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

《算法竞赛入门经典——训练指南》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法设计基础第1章算法设计基础在《算法竞赛入门经典》一书中，已经讨论过算法分析、渐进时间复杂度等基本概念，以及分治、贪心、动态规划等常见的算法设计方法。本章是《算法竞赛入门经典》的延伸，通过例题介绍更多的算法设计方法和技巧。1.1思维的体操例题1勇者斗恶龙（TheDragonofLoowater,UVa11292）你的王国里有一条n个头的恶龙，你希望雇一些骑士把它杀死（即砍掉所有头）。村里有m个骑士可以雇佣，一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头，且需要支付x个金币。如何雇佣骑士才能砍掉恶龙的所有头，且需要支付的金

2、币最少？注意，一个骑士只能砍一个头（且不能被雇佣两次）。【输入格式】输入包含多组数据。每组数据的第一行为正整数n和m（1≤n,m≤20 000）；以下n行每行为一个整数，即恶龙每个头的直径；以下m行每行为一个整数，即每个骑士的能力。输入结束标志为n=m=0。【输出格式】对于每组数据，输出最少花费。如果无解，输出“Loowaterisdoomed!”。【样例输入】235478421551000【样例输出】11Loowaterisdoomed!·103·第1章算法设计基础【分析】能力强的骑士开价高是合理的，但如果被你派去砍一个很弱的头，就

3、是浪费人才了。因此，可以把雇佣来的骑士按照能力从小到大排序，所有头按照直径从小到大排序，一个一个砍就可以了。当然，不能砍掉“当前需要砍的头”的骑士就不要雇佣了。代码如下。#include#include//因为用到了sortusingnamespacestd;constintmaxn=20000+5;intA[maxn],B[maxn];intmain(){intn,m;while(scanf("%d%d",&n,&m)==2&&n&&m){for(inti=0;i

4、",&A[i]);for(inti=0;i=A[cur]){cost+=B[i];//雇佣该骑士if(++cur==n)break;//如果头已经砍完，及时退出循环}if(cur

5、}例题2突击战（CommandoWar,UVa11729）你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bi分钟交待任务，然后他会立刻独立地、无间断地执行Ji分钟后完成任务。你需要选择交待任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。注意，不能同时给两个部下交待任务，但部下们可以同时执行他们各自的任务。【输入格式】输入包含多组数据，每组数据的第一行为部下的个数N（1≤N≤1 000）；以下N行每行两个正整数B和J（1≤B≤10 000，1≤J≤10 000），即交待任务的时间和执行任务的时间。输

6、入结束标志为N=0。【输出格式】对于每组数据，输出所有任务完成的最短时间。·103·第1章算法设计基础【样例输入】325322133344550【样例输出】Case1:8Case2:15【分析】直觉告诉我们，执行时间较长的任务应该先交待。于是我们想到这样一个贪心算法：按照J从大到小的顺序给各个任务排序，然后依次交待。代码如下。#include#include#includeusingnamespacestd;structJob{intj,b;booloperator<(constJ

7、ob&x)const{//运算符重载。不要忘记const修饰符returnj>x.j;}};intmain(){intn,b,j,kase=1;while(scanf("%d",&n)==1&&n){vectorv;for(inti=0;i

8、+=v[i].b;//当前任务的开始执行时间ans=max(ans,s+v[i].j);//更新任务执行完毕时的最晚时间}printf("Case%d:%d",kase++,ans);}return0;}上述代码直接