算法竞赛入门经典训练指南

第 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; = A[cur]) { if(B[i] >= A[cur]) { cost += B[i]; cost += B[i]; // 雇用该骑士 if(++cur == n) break; if(++cur == n) break; // 如果头已经砍完，及时退出循环 } if(cur 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; <> 算法的依据。 时间 交代执行 交代执行 交代执行 交待执行 时间 交代执行 交代执行 交代执行 交代执行 先后顺序是关键 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 之间的同步来加速，有兴趣的读者 可以自行搜索详细信息。