1.引言

ok啊，拖更这么长时间也是没有压力（doge）

不说啥，直接进入正题。

2.概念

这个贪心算法呢，看名字就知道，不就是每个步骤都挑最好的嘛，有啥难的。

这么说的话......其实确实，你如果真的能很快找出贪心策略那就可以这么说，但还是那句话，策略怎么找是个问题。

讲这么多，还没讲一下定义（虽然不讲感觉也能猜出来）：

贪心算法就是在特定问题中每一次计算都做出最好的选择，举个例子：

本蒟蒻去商店买东西，这商店呢，规矩是每天商品的价格都是原来的2倍（这商店不得不说是真敢这么加价啊），且商品不继续进货（怎么开下去的）。而我这个蒟蒻呢，很有钱，但很吝啬，想要花最少的钱把商店里的东西全买一遍，于是本蒟蒻就开始定制一个计划。

这个商店位于郊区，人迹罕至，除了本蒟蒻没有人来买（6），经过我大脑飞快运转后，我想到了可以这样：每天都去挑选最贵的，这样到最后钱耗得就是最少的啦！

这个例子有点抽象，但能看懂就行（doge），其中我这个“天才策略”就是贪心策略啦，我们可以来验算一下：当商店有3件物品，价格分别为100 200 300，当我们用其他的方法来买的时候（以200 -100-300为例）,我们可以得出这种方法需要200*1+100*2+300*3=1300元，但当我们用我这种天才方法（300-200-100）时会发现只需要300*1+200*2+100*3=1000元！整整少了300元，够吃顿火锅了。

我们转化到编程中，大概就是这样：（n为物品数量，ai为每个物品的价值（ai <= 1000），商店物品数量不超过10^5个）

#include <bits/stdc++.h>
using namespace std;int n,a[100005];
long long ans;                   //这个问题是我自己临时想的，也不知道，开个ll保险点bool cmp(int x,int y){return x > y;                //比较函数（bool型哈），即sort排序的方法，结构体排序就要用到，这里的x>y是指大的排前面，小的往后，即从大到小排列
}int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];}sort(a+1,a+n+1,cmp);         //这里本蒟蒻输入是1~n，所以根据sort不包头不包尾性质（自创），要在前后各+1for(int i = 1;i <= n;i++){ans += a[i]*i;           //i为第几天，这时a数组已排好序，即第i天买第a[i]个物品}cout << ans;                 //输出
}

so，大概都理解了吧~

接下来我们来说一下这个贪心算法的关键：贪心策略的选择。你想想，有些贪心问题吧，它会有many的方法，我们要在其中选择出正确的方法，这种方法有一个极其重要的性质——无后效性。听起来很高大上对不对？其实吧，就是后面的结果不会影响到前面的结果（以上面那个例子来说，就是我第2天买完东西后商店老板不会再说：“我把第1天的价格提高两倍了，你得给我补回来。”毕竟这样就成黑商了）。

3.演练

既然大概懂了，那么，来点料吧呵呵...（邪笑）

1.排队接水

这题目也可以说是老得没边了，贪心经典问题（放在某卡牌里几乎是绝版级的了）：

题目描述

有 n个人在一个水龙头前排队接水，假如每个人接水的时间为 Ti，请编程找出这 n个人排队的一种顺序，使得 n个人的平均等待时间最小。

输入描述

第一行为一个整数 n。

第二行 n个整数，第 i个整数 Ti表示第 i个人的接水时间 Ti​。

输出描述

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

样例1

输入

10 
56 12 1 99 1000 234 33 55 99 812

输出

3 2 7 8 1 4 9 6 10 5
291.90

提示

1≤n≤1000，1≤ti≤10^6，不保证 ti 不重复。

我们直接来看题。

这道题其实很简单，有十个人去接水，每个人接水都要一定时间（也许容积不同吧，全家桶和马桶不是一个概念），每个人接水时，在后面排队的是需要等待的，也就是说呢，一个人就会浪费后面x个人的时间，也就是说他会浪费ti*x的时间！太可恶了！

开个玩笑。

这道题我们其实可以发现，当后面排队的人越多，他所耗的平均时间就会越长，也就是说，这个人接水的时间越长，平均时间也就越长。

可能这种解释比较模糊，我们以样例来解释一下：

我们样例的输入中，可以发现1是最短的，1000是最长的。我们以这两个为开始，假设让时长为1的人去接，那么10个人的总等待时长就是9*1=9，其次再让1000来的话，那么这两人耗费所有人的总时长就是1*9+1000*8=8009，而如果我们反过来，让1000的那个先接，1后接，则耗费的总时长就是1000*9+1*8=9008 > 8009，这样我们就可以发现，我们把小的放在前面，大的放在后面（也就是从小到大排）就可以得出最少的总时长和平均时长。

或者这样解释，我们假设这10个人已经排好队，则我们所要的时长之和就是9*a[1]+8*a[2]+7*a[3]+6*a[4]+...+1*a[9]+0*a[10]，这时我们发现，当我们把a[1],a[2]..a[10]从小到大排列后可以得出最终结果是最小的。

因此，我们可以编出以下代码：

#include <bits/stdc++.h>
using namespace std;int n;
struct node{int num,time;                //这里定义结构体是为了方便把每个人的编号给记录一下
}t[100005];
double ans;                      //平均时长保留两位小数，用浮点型bool cmp(node x,node y){return x.time < y.time;      //这里的x.time<y.time就是指按每个元素的time大小从小到大排
}int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> t[i].time;        //输入每个人所需的时间t[i].num = i;            //输入顺序即每个人的编号}sort(t+1,t+n+1,cmp);         //排序，cmp上面解释了for(int i = 1;i <= n;i++){ cout << t[i].num << " "; //这里先输出最优排序中每个人的顺序（即编号，结构体排序中所有元素会随着所排序的元素一起移动）}for(int i = 1;i <= n;i++){ans += 1.0*t[i].time*(n-i);     //1.0*是为了把这个平均时间转化为浮点型，后面(n-i)只后面等待的人数} cout << endl;                           //换行别忘了！！！cout << fixed << setprecision(2) << 1.0*ans/n;  //1.0还是转换（毕竟后面有整除n），前面的fixed和setprecision(2)这种就是保留两位小数的意思，有点复杂，可以用printf()，见下
//  printf("%.2f",1.0*ans/n);  return 0;                   //好习惯是需要养成的（虽然上面那个例子没写，但不要学我不写哈）  
}

十分抽象，不说什么了，继续。

2.选修课

题目描述

【题目描述】

周末有n门选修课, 小猴要在n门选修课中选择尽可能多的课程

已知每门课程的开始时间和结束时间, 不能选时间段上有重复的课程.

---

【输入格式】

第一行是一个整数n(1≤n≤1000)

接下来n行，每行是2个整数ai,bi(0≤ai<bi≤10^9)，表示每门课程开始、结束的时间。

【输出格式】

一个整数, 小猴能选的最大课程数量

---

【输入样例#1】

3
0 2
2 4
1 3

【输出样例#1】

2

这道题其实吧，也不难，总归要排序。

但它有一个起始时间和终止时间，到底排哪个是个问题。

其实吧，你仔细想想，这道题如果你想要去做的话，那一定要让这个时间尽量连接在一起，每一段时间都不浪费。

既然这样，那我们发现结束时间越早，那可选的课程就应该更多，即用结束时间排序更为合理。

同时我们再来想一下贪心策略，结束时间虽然早，但是我们还是要判断结束时间第二早的那门课程的开始时间是否合理，如果合理就选，不合理就继续选择第三早的。

我们用样例解释一下：

给出三门课，按结束时间排序后变成了a[1] = 0 2,a[2] = 1 3,a[3] = 2 4。首先我们肯定要选第一个a[1]，然后这时的结束时间便是2，接下来如果我们要选a[2]的话，会发现开始时间<2，时间有重复，不能选；我们再看a[3]，它的开始时间是2，刚好等于a[1]的结束时间，可以选。从而我们选a[1]、a[3]两节课是最佳选择。

由此，我们编出以下代码：

#include <bits/stdc++.h> 
//这里给大家讲一下，在cmath库中有y1是被定义的函数，都是用万能头后这个y1就不能作为变量了，所以当你要用y1这个名称的时候就老老实实将一个个库写下来，别用万能（会报错）
using namespace std;int n,l,ans;                          //l是选定某节课后最早可以开始上课的时间
struct node{int a,b;                          //a为开始时间，b为结束时间
}c[1005];bool cmp(node x,node y){              //比较函数return x.b < y.b;                
}int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> c[i].a >> c[i].b;     }sort(c+1,c+n+1,cmp);             //以结束时间排序for(int i = 1;i <= n;i++){if(c[i].a >= l){             //如果这门课程开始时间比上一节课的结束时间晚就选中ans++;                   //统计课程数量l = c[i].b;              //更新最晚时间}}cout << ans;return 0;
}

也是很简单。

3.Best Cow Line

题目描述

FJ带着他的N头奶牛去参加年度最佳农场评选.

评选的组织者会将来自同一个农场的奶牛按照列队的顺序进行登记, 并且只登记每只奶牛名字的首字母. 如果FJ让Bessie, Sylvia, 和 Dora按这个顺序排好队,FJ的农场就会被登记为字符串"BSD". 登记后所得到的的字符串的字典序最小的农场将会被评为年度最佳农场.(字典序是指从前到后比较两个字符串大小的方法，首先比较第一个字符，如果不同则第1个字符较小的字符串更小，如果相同，继续比较第2个字符...如此继续，来比较整个字符串的大小)

FJ已经将奶牛排好队, 现在他要进行以下两种操作共N次, 将奶牛排一个新队:

1.将原队伍排第一的奶牛加入新队伍的末尾

2.将原队伍排最后的奶牛加入新队伍的末尾

FJ想要通过以上两种操作, 构造字典序尽可能小的新队伍. 输入原队伍的顺序，输出字典序最小的新队伍.

输入描述

第一行一个正整数N, 表示奶牛的数量(N≤2000)

接下来N行，每行一个大写英文字母, 代表原队伍每只奶牛的名字首字母.

输出描述

输出字典序最小的新队伍, 每输出80个字符就换行.

样例1

输入

6
A
C
D
B
C
B

输出

ABCBCD

这道题也难不倒哪里去，我们稍微看看就会发现其实就两个判断：如果队首跟队尾的字母不一样，那么就返回字典序小的那个，否则就继续往后比。

没了，就这么简单。

直接上代码：

#include<bits/stdc++.h>
using namespace std;int n;
string ans;                      //新队列
char s[2005];                    //记录原队列bool check(int l,int r){         //比较队首和队尾的函数if(s[l] != s[r])                  return s[l] < s[r];      //不一样就返回，这里如果s[l]比s[r]小就会返回true，反之亦然else if(s[l] == s[r])return check(++l,--r);   //否则继续往后比return true;                 //比到最后都是相等就直接随便返回其中任意一个
}int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> s[i];}int l = 1,r = n;             //这里类似二分算法，l相当于队首，r相当于队尾for(int i = 1;i <= n;i++){if(check(l,r)){ans += s[l];         //如果队首小，ans字符串就插入队首l++;                 //队首已经出列了，现在的队首就是后一个}else{                   //反之亦然ans += s[r];r--;}if(i%80 == 0){           //满80进一ans += '\n';         //添加换行符}}cout << ans;                 //输出最后的字符串return 0;
}

真的不是很难。

4.[NOIP 2002 提高组] 均分纸牌

这道题我也不想多说什么了，二十三年的老题，和刘禹锡“二十三年弃置身”的时间一样了。

题目描述

有 N 堆纸牌，编号分别为 1,2,…,N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N−1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 N=4 时，4 堆纸牌数分别为 9,8,17,6。

移动 3 次可达到目的：

• 从第三堆取 4 张牌放到第四堆，此时每堆纸牌数分别为 9,8,13,10。
• 从第三堆取 3 张牌放到第二堆，此时每堆纸牌数分别为 9,11,10,10。
• 从第二堆取 1 张牌放到第一堆，此时每堆纸牌数分别为 10,10,10,10。

输入格式

第一行共一个整数 N，表示纸牌堆数。
第二行共 N 个整数 A1​,A2​,…,AN​，表示每堆纸牌初始时的纸牌数。

输出格式

共一行，即所有堆均达到相等时的最少移动次数。

输入输出样例

输入 #1

4
9 8 17 6

输出 #1

3

说明/提示

对于 100% 的数据，1≤N≤100，1≤Ai​≤10000。

这题目其实也很简单，首先，因为他没说无法均等的情况，所以默认这些卡牌数字之和是能被n整除的，即均等时每张牌的数值。

接下来就是那这个平均数值来比较移动次数了，我们仔细看一下，其实任何一种情况都最多只需要n-1次即可均分（1给/拿2，2给/拿3...n-1给/拿n，最后肯定能保证n为平均值），因此，我们只需要定义一个变量来存储变换次数，而当这堆纸牌刚好卡在平均数上，那么就可以跳过了，具体操作如下：

for(int i = 1;i <= n-1;i++){         //第n堆能保证为平均数if(a[i]-sum == 0) continue;      //当这堆牌刚好在平均数上时就跳过，同时计数变量不变a[i+1] = a[i]-sum+a[i+1];        //否则就将下一堆的牌给它调到平均数（用后一堆即为无后效性，不会影响前面已摆好的牌）ans++;                           //计数变量，增加移动次数
}

那么再加上其他的输入输出，即可得出最终代码：

#include <bits/stdc++.h>
using namespace std;int n,sum,ans;
int a[105];int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];sum += a[i];}sum /= n;for(int i = 1;i <= n-1;i++){if(a[i]-sum == 0) continue;a[i+1] = a[i]-sum+a[i+1];ans++;}cout << ans;return 0;
}

撒花✿✿ヽ(°▽°)ノ✿

4.习题

也是又到了难为大佬检查学习成果的时候了，来叭hh（邪笑）

1.导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是 <= 50000的正整数），计算要拦截所有导弹，最少要配备多少套这种导弹拦截系统。

输入描述

第1行一个正整数n （n≤1000）

第2行n个正整数, 不超过50000, 以空格分隔

输出描述

1行，表示如果要拦截所有导弹，最少要配备多少套这种导弹拦截系统。

样例1

输入

8
389 207 155 300 299 170 158 65

输出

2

2.智力大冲浪

题目描述

小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：

首先，比赛时间分为n个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi​，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。 主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱！

---

【输入格式】

输入共四行。

第一行为m，表示一开始奖励给每位参赛者的钱；

第二行为n，表示有n个小游戏；

第三行有n个数，分别表示游戏1到n的规定完成期限；

第四行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。

【输出格式】

输出仅一行，表示小伟能赢取最多的钱。

---

【输入样例#1】

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

【输出样例#1】

9950

---

【数据说明】

对于100%的数据，有n≤500，1≤ti≤n。

3.红苹果和绿苹果

【题目描述】

你想要吃X个红苹果和Y个绿苹果。

目前有A个红苹果，美味度分别是p1,p2,⋯ ,pA​；B个绿苹果，美味度分别是q1,q2,⋯ ,qB；CC个无色苹果，美味度分别是r1,r2,⋯ ,rC​。

无色苹果可以染色成红苹果或者绿苹果。选择若干个（可以是0个）无色苹果，染成合适的颜色，使得你可以吃到X个红苹果和Y个绿苹果，并且使得吃到的苹果的美味度总和最大。输出最大的总和。

---

【输入格式】

第1行，5个整数X,Y,A,B,C

第2行，A个整数p1,p2,⋯ ,pA

第3行，B个整数q1,q2,⋯ ,qB

第4行，C个整数r1,r2,⋯ ,rC

【输出格式】

可以吃到的最大的美味度总和

---

【输入样例#1】

1 2 2 2 1
2 4
5 1
3

【输出样例#1】

12

【样例#1说明】

吃第2个红苹果，第1个绿苹果，将第1个无色苹果染成绿苹果吃掉。美味度总和为12。

---

【输入样例#2】

2 2 2 2 2
8 6
9 1
2 1

【输出样例#2】

25

---

【输入样例#3】

2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4

【输出样例#3】

74

---

【数据说明】

1≤X≤A≤10^5

1≤Y≤B≤10^5

1≤C≤10^5

1≤pi,qi,ri≤10^9

4.数列分段 Section I

题目描述

对于给定的一个长度为 N的正整数数列 Ai​，现要将其分成连续的若干段，并且每段和不超过 M（可以等于M），问最少能将其分成多少段使得满足要求。

输入描述

第1行包含两个正整数 N,M，表示了数列 Ai的长度与每段和的最大值，第 2行包含 N个空格隔开的非负整数 Ai，如题目所述。

输出描述

一个正整数，输出最少划分的段数。

样例1

输入

5 6
4 2 4 5 1

输出

3

提示

对于20%的数据，有N≤10

对于40%的数据，有N≤1000；

对于100%的数据，有N≤100000,M≤10^9，M大于所有数的最大值，Ai​之和不超过10^9。

将数列如下划分：

[4][24][51]

第1段和为4，第2段和为6，第3段和为6均满足和不超过M=6，并可以证明3是最少划分的段数。

5.小结

其实也没啥可总结的，反正贪心这种算法也是用处极广的一种算法，只要能掌握策略的选取（无后效性）基本就可以解决了，没什么特别难的东西。接下来我们将进入一个极其重要的算法——动态规划，我将会用5篇左右来具体阐述动态规划的各种变形，这都是后话了，886~~~~

上一章：广度优先搜索算法2                          下一章：动态规划1（序列型动规+最长上升子序列）（未完工）