第 1章 算法设计基础 算法设计基础
在《算法竞赛入门经典（第2版）》一书中，已经讨论过算法分析、渐进时间复杂度等基本概念，以及分治、贪心、动态规划等常见的算法设计方法。本章是《算法竞赛入门经典（第2版）》的延伸，通过例题介绍更多的算法设计方法和技巧。
1.1 思维的体操 例题1 勇者斗恶龙（The Dragon of Loowater, UVa 11292）
假设你是一位国王，你的王国里有一条n个头的恶龙，你希望雇一些骑士把它杀死（即砍掉恶龙的所有头）。王国里有m个骑士可以雇用，一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头，且需要支付x个金币。如何雇用骑士才能砍掉恶龙的所有头，且需要支付的金币最少？注意，一个骑士只能砍一个头（且不能被雇用两次）。
【输入格式】
输入包含多组数据。每组数据：第一行为正整数n和m（1≤n,m≤20 000）；接下来n行每行为一个正整数，即恶龙每个头的直径；再接下来m行每行为一个正整数，即每个骑士的能力。输入结束标志为n=m=0。
【输出格式】
对于每组数据，输出最少花费。如果无解，输出“Loowater is doomed!”。
【样例输入】
2 3
5
4
7
8
4
2 1
5
5
10
0
【样例输出】
11
Loowater is doomed!
【分析】
能力强的骑士开价高是合理的，但如果被你派去砍恶龙的一个很弱的头，就是浪费人
算法竞赛入门经典—训练指南
·2·
才了。因此，可以把雇用来的骑士按照能力从小到大排序，把恶龙的所有头按照直径从小到大排序，一个一个砍就可以了。当然，不能砍掉“当前需要砍的头”的骑士就不要雇用了。代码如下。
#include
#include // 因为用到了 sort
using namespace std;
const int maxn = 20000 + 5;
int A[maxn], B[maxn];
int main() {
int n, m;
while(scanf("%d%d", &n, m) == 2 && n { while(scanf("%d%d", &n, m) == 2 && n {
for(int i = 0; < n; i++) scanf("%d", &A[i]); for(int i = 0; < n; i++) scanf("%d", &A[i]);
for(int i = 0; < m; i++) scanf("%d", &B[i]); for(int i = 0; < m; i++) scanf("%d", &B[i]);
sort(A, A+n);
sort(B, B+m);
int cur = 0; int cur = 0; // 当前需要砍掉的头编号
int cost = 0; int cost = 0; // 当前总费用
for(int i = 0; < m; i++) for(int i = 0; < m; i++)
if(B[i] >= A[cur]) { if(B[i] >= A[cur]) {
cost += B[i]; cost += B[i]; // 雇用该骑士
if(++cur == n) break; if(++cur == n) break; // 如果头已经砍完，及时退出循环
}
if(cur < n) printf("Loowater is doomed! if(cur < n) printf("Loowater is doomed! \n");
else p rintf("%d \n", cost); n", cost);
}
return 0;
}
例题2 突击战（Commando War, UVa 11729）
假设你带领团队去执行一组突击任务，你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bi分钟交代任务，然后他会立刻独立地、无间断地执行Ji分钟后完成任务。你需要选择交代任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。注意，不能同时给两个部下交代任务，但部下们可以同时执行他们各自的任务。
【输入格式】
输入包含多组数据。每组数据：第一行为部下的个数n（1≤n≤1000）；接下来n行每行为两个正整数B和J（1≤B≤10 000，1≤J≤10 000），即交代任务的时间和执行任务的时间。输入结束标志为n=0。
【输出格式】
对于每组数据，输出所有任务完成的最短时间。
【样例输入】
3
2 5
第 1 章 算法设计基础
·3·
3 2
2 1
3
3
4
5
0
【样例输出】
Case 1: 8
Case 2: 15
【分析】
直觉告诉我们，执行时间较长的任务应该先交代。于是我们想到这样一个贪心算法：按照J从大到小的顺序给各个任务排序，然后依次交代。代码如下。
#include
#include
#include
using namespace std;
struct Job {
int j, b;
bool operator < (const Job& x) { bool operator < (const Job& x) { // 运算符重载，不要忘记 const 修饰符
return j > x.j;
}
};
int main() {
int n, b, j, kase = 1; int n, b, j, kase = 1;
while(scanf("%d", &n) == 1 && { &n) == 1 && {
vector v;
for(int i = 0; < n; i++) { for(int i = 0; < n; i++) {
scanf("%d%d", &b, j); v.push_back((Job){j,b}); scanf("%d%d", &b, j); v.push_back((Job){j,b});
}
sort(v.begin(), end()); sort(v.begin(), end()); // 使用 Job 类自己的 < 运算符排序 运算符排序
int s = 0;
int ans = 0;
for(int i = 0; < n; i++) { for(int i = 0; < n; i++) {
s += v[i].b; += v[i].b; // 当前任务的开始执行时间
ans = max(ans, s+v[i].j); ans = max(ans, s+v[i].j); // 更新任务执行完毕时的最晚间
}
printf("Case %d: d \n", kase++, ans);
}
return 0;
}
上述代码直接交上去就可以通过测试了。
可是为什么这样做是对的呢？假设我们交换两个相邻的任务X和Y（交换前X在Y之
算法竞赛入门经典—训练指南
·4·
前，交换后Y 在X 之前），不难发现这对其他任务的完成时间没有影响，那么这两个任务呢？
❑ 情况一：交换之前，任务Y 比X 先结束，如图1-1（a）所示。不难发现，交换之后X
的结束时间延后，Y 的结束时间提前，最终结果不会变好。
❑ 情况二：交换之前，X 比Y 先结束，则交换后结果变好的充要条件是：交换后X 的结
束时间比交换前Y 的结束时间早（交换后Y 的结束时间肯定变早了）。反之，如果出现
如图1-1（b）所示的情况，则交换后的结果不会变好，交换后结果变好的充要条件可
以写成B[Y]+B[X]+J[X]
算法的依据。
时间
交代执行
交代执行
交代执行
交待执行
时间
交代执行
交代执行
交代执行
交代执行
先后顺序是关键
B[Y]+B[X]+J[X]
B[X]+B[Y]+J[Y]
X
Y
Y
X
X
Y
Y
X
(a) (b)
图 1-1
例题3 分金币（Spreading the Wealth, UVa 11300）
圆桌旁坐着n 个人，每人有一定数量的金币，金币总数能被n 整除。每个人可以给他
左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币
数量的最小值。比如，n=4，且4 个人的金币数量分别为1,2,5,4 时，只需转移4 枚金币（第
3 个人给第2 个人2 枚金币，第2 个人和第4 个人分别给第1 个人1 枚金币）即可实现每人
手中的金币数目相等。
【输入格式】
输入包含多组数据。每组数据：第一行为正整数n（n≤1 000 000），以下n 行每行为
一个正整数，按逆时针顺序给出每个人拥有的金币数。输入结束标志为文件结束符（EOF）。
【输出格式】
对于每组数据，输出被转手金币数量的最小值。输入保证这个值在64 位无符号整数范
围内。
【样例输入】
3
100
100
100
4
1
第1 章 算法设计基础
·5·
2
5
4
【样例输出】
0
4
【分析】
这道题目看起来很复杂，让我们慢慢分析。首先，最终每个人的金币数量可以计算出
来，它等于金币总数除以人数n。接下来我们用M 来表示每人最终拥有的金币数。
假设有4 个人，按逆时针顺序编号为1, 2, 3, 4。假设1 号给2 号3 枚金币，然后2 号又
给1 号5 枚金币，这实际上等价于2 号给1 号2 枚金币，而1 号什么也没给2 号。这样，
可以设x2 表示2 号给了1 号多少个金币。如果x2<0，说明实际上是1 号给了2 号-x2 枚金币。
同理，可以设x1，x3，x4，其含义类似。注意，由于是环形，x1 指的是1 号给4 号多少金币。
现在假设编号为i 的人初始有Ai 枚金币。对于1 号来说，他给了4 号x1 枚金币，还剩
Ai-x1 枚；但因为2 号给了他x2 枚金币，所以最后还剩A1-x1+x2 枚金币。根据题设，该金币
数等于M。换句话说，我们得到了一个方程：A1-x1+x2=M。
同理，对于第2 个人，有A2-x2+x3=M。最终，我们可以得到n 个方程，一共有n 个变
量，是不是可以直接解方程组了呢？很显然，还不行。因为从前n-1 个方程可以推导出最
后一个方程（想一想，为什么）。所以，实际上只有n-1 个方程是有用的。
尽管无法直接解出答案，但我们还是可以尝试着用x1 表示出其他的xi，则本题就变成
了单变量的极值问题。
对于第1 个人，A1-x1+x2=M x2=M-A1+x1=x1-C1（C1=A1-M）
对于第2 个人，A2-x2+x3=M x3=M-A2+x2=2M-A1-A2+x1=x1-C2（C2=A1+A2-2M）
对于第3 个人，A3-x3+x4=M x4=M-A3+x3=3M-A1-A2-A3+x1=x1-C3（C3=A1+A2+ A3-3M）
…
对于第n 个人，An-xn+x1=M。这是一个多余的等式，并不能给我们更多的信息（想一
想，为什么）。
我们希望所有xi 的绝对值之和尽量小，即1 1 1 1 2 1 1 | | | | | | | | n x x C x C x C − + − + − + + − 要最
小。注意到 |x1-Ci| 的几何意义是数轴上点x1 到点Ci 的距离，所以问题变成了：给定数轴上
的n 个点，找出一个到它们的距离之和尽量小的点。
下一步可能有些跳跃。不难猜到，这个最优的x1 就是这些数的“中位数”（即排序以
后位于中间的数），因此只需要排个序就可以了。性急的读者可能又想跳过证明了，但是
笔者希望您这次能好好读一读，因为它实在是太优美、太巧妙了，而且在不少其他题目中
也能用上（我们很快就会再见到一例）。
注意，我们要证明的是：给定数轴上的n 个点，在数轴上的所有点中，中位数离所有
顶点的距离之和最小。凡是能转化为这个模型的题目都可以用中位数求解，并不只适用于
本题。
算法竞赛入门经典—训练指南
·6·
让我们把数轴和上面的点画出来，如图1-2 所示。
图 1-2
任意找一个点，比如图1-2 中的灰点。它左边有4 个输入点，右边有2 个输入点。把它
往左移动一点，不要移得太多，以免碰到输入点。假设移动了d 单位距离，则灰点左边4
个点到它的距离各减少了d，右边的两个点到它的距离各增加了d，但总的来说，距离之和
减少了2d。
如果灰点的左边有2 个点，右边有4 个点，道理类似，不过应该向右移动。换句话说，
只要灰点左右的输入点不一样多，就不是最优解。什么情况下左右的输入点一样多呢？如
果输入点一共有奇数个，则灰点必须和中间的那个点重合（中位数）；如果有偶数个，则
灰点可以位于最中间的两个点之间的任意位置（还是中位数）。代码如下。
#include
#include
using namespace std;
const int maxn = 1000000 + 10;
long long A[maxn], C[maxn], tot, M;
int main() {
int n;
while(scanf("%d", &n) == 1) { //输入数据大，scanf 比cin 快
tot = 0;
//用%lld 输入long long
for(int i = 1; i <= n; i++) { scanf("%lld", &A[i]); tot += A[i]; }
M = tot / n;
C[0] = 0;
for(int i = 1; i < n; i++) C[i] = C[i-1] + A[i] - M; //递推C 数组
sort(C, C+n);
long long x1 = C[n/2], ans = 0; //计算x1
//把x1 代入，计算转手的总金币数
for(int i = 0; i < n; i++) ans += abs(x1 - C[i]);
printf("%lld\n", ans);
}
return 0;
}
程序本身并没有太多技巧可言，但需要注意的是long long 的输入输出。在《算法竞赛
入门经典（第2 版）》中我们已经解释过了，%lld 这个占位符并不是跨平台的。比如，Windows
下的mingw 需要用%I64d 而不是%lld。虽然cin/cout 没有这个问题，但是本题输入量比较大，
cin/cout 会很慢。有两个解决方案：一是自己编写输入输出函数（前面已经给过范例），二
是使用ios::sync_ with_stdio(false)，通过关闭ios 和stdio 之间的同步来加速，有兴趣的读者
可以自行搜索详细信息。
![《算法竞赛入门经典——训练指南升级版》[29M]百度网盘|亲测有效|pdf下载](/uploads/s0309/e4c2092e3c7d412c.jpg)
