《算法竞赛入门经典训练指南》例题一（UVa11292）
基础贪心，没什么需要多讲的，直接放上代码。有一点要注意的是我第一遍写的时候竟然犯了两个错误。
错误点
- 将dragon、knight与i、j对应错误了，仔细一想人有先后对应的天性，下次设置i、j时还是老老实实根据输入顺序来，避免出错
- 第23行遗漏了(j<n)这个条件，使得在龙已经全被砍头的情况下却雇佣了剩余的骑士。
本题重点
砍龙头的时候设置两个指针，分别移动，使用频率挺高的一个小技巧，不难，但是挺重要的。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5
6 const int MAXN=20000;
7 int dragon[MAXN];
8 int knight[MAXN];
9
10 int main()
11 {
12 int n,m;
13 while (scanf("%d%d",&n,&m))
14 {
15 int sum=0;
16 if ((n==m) && (n==0)) break;
17 for (int i=0;i<n;i++) scanf("%d",&dragon[i]);
18 for (int i=0;i<m;i++) scanf("%d",&knight[i]);
19 sort(dragon,dragon+n);
20 sort(knight,knight+m);
21 int i=0,j=0;
22
23 while ((i<m) && (j<n))
24 {
25 if (knight[i]>=dragon[j])
26 {
27 j++;
28 sum+=knight[i];
29 }
30 i++;
31 }
32 if (j<n) cout<<"Loowater is doomed!"<<endl;
33 else cout<<sum<<endl;
34 }
35 return 0;
36 }
《算法竞赛入门经典训练指南》例题二（UVa11729）
较基础贪心，关键是证明“执行时间长的先交代，总时间最短”这个命题以及“在执行时间相同的情况下如何安排次序”这个问题。当然事实证明执行时间相同的情况下，如何安排次序是无所谓的。书上已经讲得很清楚了，这里不进行过多阐述。（详见P4图解）注意的是书上的图（b）下方有误，应为B[Y]+B[X]+J[Y]。
对于书中标程的一些说明
- 书上用到了<vector>，我也不知道比赛的时候能不能用（哪个神犇来告诉我一下），也觉得没有必要用，写程序的时候就没有用到<vector>了。
- 这里有个非常重要的struct比较大小的简便写法，刚开始学C++要重点学习一下。其中Rec表示我们设置的记录。
1 struct Rec 2 { 3 int b,j; 4 bool operator < (const Rec& x) const 5 { 6 return j<x.j; 7 } 8 }; - 书中循环的判断条件中出现的scanf(“%d”,&n) == 1的含义即为输入的n为一个数字。因为scanf判断输入正确时返回值为数字，若非法则返回值为0，循环中 止。在这里其实可以不必用的，但在诸如：最后一位用字符表示中止循环条件时，非常好用。
错误点
- 第一遍的时候全然忘记sort是从小到大排序的了，于是耍了一个小聪明把return j<x.j中的小于号改为大于号即可，觉得自己超机智的时候发现树上就是这么干的。或者老老实实地把循环敲为for (int i=n-1;i>=0;i++)。个人推荐后者，因为（个人实践表明）耍小聪明总是没有好下场的。
本题重点
对于贪心的证明是个重点，代码28-33行的小技巧在执行任务类的题目里非常常见，要重点牢记
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int MAXN=1000;
6 int b[MAXN];
7 int j[MAXN];
8
9 struct task
10 {
11 int b,j;
12 bool operator < (const task& x) const
13 {
14 return j>x.j;//因为要从大到小排所以这里变动一下
15 }
16 };
17
18 int main()
19 {
20 int cases=0,n;
21 while (scanf("%d",&n))
22 {
23 cases++;
24 if (n==0) break;
25 task kase[MAXN];
26 for (int i=0;i<n;i++) scanf("%d%d",&kase[i].b,&kase[i].j);
27 sort(kase,kase+n);
28 int m=0,ans=0;
29 for (int i=0;i<n;i++)
30 {
31 m+=kase[i].b;
32 ans=max(ans,m+kase[i].j);
33 }
34 cout<<"Case "<<cases<<": "<<ans<<endl;
35 }
36 return 0;
37 }
以下为《挑战程序设计竞赛》中贪心部分
2.2.1硬币问题（UVa11292）
没什么需要说的，秒杀题。
错误点
- 一开始犯了一个小错，注意17行为a-v[i]>=0需要取等，否则余额刚好等于当前面值时就不会算了
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4
5 int a;
6 int v[6]={1,5,10,50,100,500};
7 int c[6];
8
9 int main()
10 {
11 scanf("%d%d%d%d%d%d%d",&c[0],&c[1],&c[2],&c[3],&c[4],&c[5],&a);
12 int i=5;
13 int sum=0;
14 while ((a>0) && (i>=0))
15 {
16 int j=0;
17 while ((0<=a-v[i]) && (j<c[i])) //这里是0<=a-v[i]
18 {
19 j++;
20 a-=v[i];
21 }
22 sum+=j;
23 i--;
24 }
25 cout<<sum<<endl;
顺便说一下虽然是一道极其简单的题，但是看了书中的标程，觉得自己的程序写得好丑(╯>д<)╯于是按照标程的方式又写了一个简洁的
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 using namespace std;
5
6 int a;
7 int v[6]={1,5,10,50,100,500};
8 int c[6];
9
10 int main()
11 {
12 scanf("%d%d%d%d%d%d%d",&c[0],&c[1],&c[2],&c[3],&c[4],&c[5],&a);
13 int sum=0;
14 for (int i=5;i>=0;i--)
15 {
16 sum+=min((a/v[i]),c[i]);
17 a-=min(a/v[i],c[i])*v[i];
18 }
19 cout<<sum<<endl;
20 }
2.2.2区间调度问题
较难贪心，但题目本身非常标准。重点在于对选取方法的否定与证明。
对书中内容的补充（关于区间调度问题），这里推荐一个CSDN的博文，以后我会细谈的，请点击；对于本体的命题的证明方法请戳，因为与本体相关，把证明部分在此引用一下
命题1.1 当i>=1时，该算法所接受的第i个区间的右端点坐标fi<=某最优解中的第i个区间的右端点坐标gi。
该命题可以运用数学归纳法来证明。对于i=1，命题显然为真，因为算法第一个选择的区间拥有最小右端点坐标。令i>1，假定论断对i-1为真，即fi-1<=gi-1。则最优解的第i个可选区间所组成的集合包含于执行该算法时第i个可选区间所组成的集合；而当算法选择第i个区间时，选的是在可选区间中右端点坐标最小的一个，所以有fi<=gi。证毕。
设该算法选出了k个区间，而最优解选出了m个区间。
命题1.2 最优解选出的区间数量m=该算法选出的区间数量k。
假设m>k，根据命题1.1，有fk<=gk。由于m>k，必然存在某区间，在gk之后开始，故也在fk之后开始。而该算法一定不会在选了第k个区间后停止，还会选择更多的区间，产生矛盾。所以m<=k,又因为m是最优解选出区间个数，所以m=k。
综上所述，算法选出的区间是最优解。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5
6 const int MAXN=100000;
7 struct task
8 {
9 int s,t;
10 bool operator < (const task& x) const
11 {
12 return t<x.t;
13 }
14 };
15
16 int main()
17 {
18 int n,last=0,ans=0;
19 task kase[MAXN];
20 scanf("%d",&n);
21 for (int i=0;i<n;i++) scanf("%d",&kase[i].s);
22 for (int i=0;i<n;i++) scanf("%d",&kase[i].t);
23 sort(kase,kase+n);
24 for (int i=0;i<n;i++)
25 {
26 if (kase[i].s>last)
27 {
28 ans++;
29 last=kase[i].t;
30 cout<<"task "<<i+1<<endl;
31 }
32 }
33 cout<<ans<<endl;
34 }
2.2.3字典序最小问题（POJ 3617）
这道题的样例十分良心，本题唯一一个陷阱就在那儿了，然而我还是一脚踩了下去。
错误点
- 输入的时候第一次把&忘记了导致程序崩溃，数组输入用scanf的时候最容易遗忘&了要注意
- 当两边字符相同的时候可能会出现分歧，需要判断。我一开始没有考虑到，所以写出来的程序是这个样子的
Wrong Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace std; 5 const int MAXN=2000; 6 7 int main() 8 { 9 int n; 10 scanf("%d",&n); 11 char s[MAXN]; 12 for (int i=0;i<n;i++) 13 { 14 getchar(); 15 scanf("%c",&s[i]); //不要忘记& 16 } 17 int i=0,j=n-1; 18 while (i<=j) 19 { 20 cout<<s[i]<<' '<<s[j]<<endl; 21 if (s[i]<=s[j]) 22 { 23 cout<<s[i];i++; 24 } 25 else 26 { 27 cout<<s[j];j--; 28 } 29 } 30 cout<<endl; 31 return 0; 32 }样例就挂掉了之后才发现_(:зゝ∠)_
- 好，再来说说我写好之后的错误。21行是i+k<=j而不是i+k<=j-k，光想着后面了这里就写错了。
- 还有28行一定要写s[i+k]>s[j-k] ，否则比较到相同时就会自动退出！这个比较就没有意义了。
- 就是这样一道水题，让我吃了两个WA（上面两点）和人生中头两个PE。 一直没弄明白到底哪里出错了，打开别人的解题报告发现没输出80个字符会换一行，去看了一下题目发现竟然有这样一句话“Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the new line.”然而我没有读懂这句话的意思，之前写题的时候看书翻译里也并没有这句话。所以大家要好好看题好好学习英语啊！
本题重点
对于字典序这类的题目，当两边相同的时候难以比较大小，此时用一个特定的方法。引用一下书中的原句：“按照字典序比较S和将S反转后的字符串S' ”。这个处理方法非常常见，要牢记
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 using namespace std;
5 const int MAXN=2000;
6
7 int main()
8 {
9 int n;
10 scanf("%d",&n);
11 char s[MAXN];
12 for (int i=0;i<n;i++)
13 {
14 getchar();
15 scanf("%c",&s[i]); //不要忘记&
16 }
17 int t=0;
18 int i=0,j=n-1;
19 while (i<=j)//通过反转字符串来比较，避免字典序相同时带来的困扰
20 {
21 bool left=false;
22 for (int k=0;i+k<=j;k++)//注意这里是i+k<=j而不是i+k<=j-k
23 {
24 if (s[i+k]<s[j-k])
25 {
26 left=true;
27 break;
28 }
29 else if (s[i+k]>s[j-k]) //s[i+k]>s[j-k]
30 {
31 left=false;
32 break;
33 }
34 }
35 if (left) cout<<s[i++];
36 else cout<<s[j--];
37 t++;
38 if (t%80==0) cout<<endl;
39 }
40 //cout<<endl;
41 return 0;
42 }
2.2.4 其它例题
1.Saruman's Army（POJ3069）
水题，不多讲了，没有任何难点。我就说一句：不要忘了排序，我写太兴奋第一次就忘掉了..
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5
6 const int MAXN=1000;
7 int x[MAXN];
8
9 int main()
10 {
11 int r,n;
12 while (scanf("%d%d",&r,&n))
13 {
14 if ((r==n) && (r==-1)) break;
15 for (int i=0;i<n;i++) scanf("%d",&x[i]);
16 sort(x,x+n);
17 int j=x[0],i=0,sum=0;
18 while (i<n)
19 {
20 while (j+r>=x[i]) i++;
21 sum++;
22 int temp=x[i-1]+r;
23 while (temp>=x[i]) i++;
24 j=x[i];
25 }
26 cout<<sum<<endl;
27 }
28 return 0;
29 }
2.Fence Repari(POJ3253)
经典题，但很容易因为固化思维跳坑，真的很容易！笔者在之前写过两次都跳坑了，这次傻歪歪又跳坑了……
错误点
1.先放一个错误版的程序，不能按照排序后由小到大来分割
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int MAXN=20000;
6 int l[MAXN];
7
8 int main()
9 {
10 int n;
11 scanf("%d",&n);
12 for (int i=0;i<n;i++) scanf("%d",&l[i]);
13 sort(l,l+n);
14 int ans=0;
15 for (int i=0;i<n;i++)
16 {
17 ans+=l[i]*(n-i);
18 }
19 ans-=l[0];
20 cout<<ans;
21 }
这里应该使用的是Huffman树，开销的合计等于各叶子节点的木板长度*深度。这里用的是简单粗暴的方法。
2.在插入排序的时候不要忘记了在范围内这个条件，否则如果合并后交换到最后，会出现0
3.ans一定要用__int64，顺便int64的下划线是两个，不是一个！
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int MAXN=20000;
6 int l[MAXN];
7
8 int main()
9 {
10 int n;
11 scanf("%d",&n);
12 for (int i=0;i<n;i++) scanf("%d",&l[i]);
13 sort(l,l+n);
14 __int64 ans;
15 ans=0;
16 for (int i=0;i<n-1;i++)
17 {
18 l[i+1]=l[i]+l[i+1];
19 ans+=l[i+1];
20 int j=i+1;
21 while ((l[j]>l[j+1]) && (j+1<n)) //不要忘记j+1<n这个条件，否则如果交换到最后就换变成0
22 {
23 int temp=l[j];
24 l[j]=l[j+1];
25 l[j+1]=temp;
26 j++;
27 }
28 }
29 cout<<ans<<endl;
30 }
对于书中标程的一些说明
书中的标程的作法是先将前两个数据排序，让指针i,j指向前两个数据。再与后面的数据比较，移动指针使得每次指向的两个数据都是最小的两个数据。将两个数据合并，加到结果里。最后用这L[i]+L[j]替换L[i]，将最后一位前移用L[N-1]替换L[j]。
要重点强调的是，在替换数据前需要判断，如果指针i指向的位置是倒数第二位，即N-1，则交换i和j，否则L[i]+L[j]会被移动到最后一位忽略掉，而L[N-1]则会保留下来，这是错误的。
本题重点
Huffman的知识点要注意。网上很多解题报告说要用STL优先队列、堆的，其实就这道题而言并不需要，不过我可能都打算写一写。以后有空回来补上这两种解法的（2015-7-4更新：已补上，详见POJ3253解题报告）。