日期：2022年5月25日

注：本博客仅供参考

概念与思路

贪心算法是指在对某一问题求解时，总是作出当前情况下的最优选择。因此，贪心算法考虑的不是整个问题的最优解，算法得到的是在某一局部环境下的最优解。

贪心算法的一般思路为：

1. 把要求解的问题分为若干个子问题；
2. 对每个子问题求解，得到子问题的局部最优解；
3. 把得到的局部最优解合为原来问题的一个解。

注意事项（尤为重要）

• 贪心算法能省去要穷尽所有可能二耗费的大量时间，但它没有考虑整个问题下的情景，因此通过该算法得到的答案，不能确定是否为整个问题的最优解。也就是说，如果要使用贪心算法，应该在证明出通过贪心得出的答案就是最优解后再使用。
• 贪心算法一般只用于求最大或最小值。
• 贪心算法只能确定某些问题的可行性范围。

代码与应用

部分背包问题（P2240）

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有N(N≤100)堆金币，第i堆金币的总重量和总价值分别是 m_i,v_i(1≤m_i,v_i≤100)。阿里巴巴有一个承重量为T(T≤1000)的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 N,T。

接下来N行，每行两个整数 m_i,v_i。

输出格式

一个实数表示答案，输出两位小数。

代码

 1 #include
 2 using namespace std;
 3 const int N=110;
 4 int n,t;
 5 struct node{
 6     int m;
 7     int v;
 8 };
 9 node a[N];
10 bool operator <(node a,node b){
11     return a.v*b.m>b.v*a.m;
12     /*用金币价值与金币质量的比值来比较不同金币的实际价值
14     return a.v*b.m>b.v*a.m的效果等同于return a.v/a.m>b.v/b.w，但由于在C++中“/”意为整除，所以需要使用其他方法代替除法*/
15 }
16 int main(){
17     scanf("%d%d",&n,&t);
18     for(int i=1;i<=n;++i)
19     {
20         scanf("%d%d",&a[i].m,&a[i].v);
21     }
22     sort(a+1,a+1+n);//重定义的的“<”会在这里用到
23     double ans=0;
24     for(int i=1;i<=n;++i)
25     {
26         if(a[i].m<=t)//当金币质量小于背包能容纳的剩余质量时，将这堆金币全部放进去
27         {
28             ans+=a[i].v;
29             t-=a[i].m;
30         }else{//当金币质量大于背包能容纳的剩余质量时，用这种金币将背包的剩余部分填满并结束循环
31             ans+=1.0*t*a[i].v/a[i].m;
32             break;
33         }
34     }
35     printf("%.2lf",ans);
36     return 0;
37 }         

排队接水（P1223）

题目描述

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

输入格式

第一行为一个整数n。

第二行n个整数，第i个整数T_i 表示第i个人的等待时间T_i。

输出格式

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

代码

 1 #include
 2 using namespace std;
 3 const int N=1000100;
 4 int n;
 5 double ave=0;
 6 struct node{
 7     int t;
 8     int code;
 9 };
10 bool operator <(node a,node b){
11     return a.t//升序排列
12 }
13 node T[N];
14 int main(){
15     scanf("%d",&n);
16     for(int i=1;i<=n;++i)
17     {
18         scanf("%d",&T[i].t);
19         T[i].code=i;
20     }
21     sort(T+1,T+1+n);
22     for(int i=1;i<=n;++i)
23     {
24         for(int j=0;jj)
25         {
26             ave+=T[j].t;
27         }
28         printf("%d ",T[i].code);
29     }
30     ave/=n;//平均等待时间为所有人需要等待的时间与人数的比值
31     printf("\n%.2lf",ave);
32     return 0;
33 }

均分纸牌（P1031）

题目描述

有NN堆纸牌，编号分别为 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堆纸牌，1≤N≤100）。

第二行为：A₁,A₂, … ,A_n? （N堆纸牌，每堆纸牌初始数，1≤A_i≤10000）。

输出格式

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

代码

 1 #include
 2 using namespace std;
 3 const int N=110;
 4 int n,a[N],ave=0,sum=0;
 5 int main(){
 6     scanf("%d",&n);
 7     for(int i=1;i<=n;++i)
 8     {
 9         scanf("%d",&a[i]);
10         ave+=a[i];
11     }
12     ave/=n;//纸牌平均数恒为定值
13     for(int i=1;i<=n;++i)
14     {
15         if(a[i]!=ave)//如果这堆纸牌不是平均值，向右边放a[i+1]-ave张纸牌
16         {
17             a[i+1]+=a[i]-ave;
18             ++sum;
19         }
20     }
21     printf("%d",sum);
22     return 0;
23 }

铺设道路（P5019）

题目描述

春春是一名道路工程师，负责铺设一条长度为n的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是n块首尾相连的区域，一开始，第i块区域下陷的深度为d_i?。

春春每天可以选择一段连续区间[L,R]，填充这段区间中的每块区域，让其下陷深度减少1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为0。

春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为0。

输入格式

输入文件包含两行，第一行包含一个整数n，表示道路的长度。 第二行包含n个整数，相邻两数间用一个空格隔开，第i个整数为d_i?。

输出格式

输出文件仅包含一个整数，即最少需要多少天才能完成任务。

代码

 1 #include
 2 using namespace std;
 3 const int N=100100;
 4 int n,d[N],sum=0;
 5 int main(){
 6     scanf("%d",&n);
 7     for(int i=1;i<=n;++i)
 8     {
 9         scanf("%d",&d[i]);
10     }
11     sum+=d[1];
12     for(int i=2;i<=n;++i)
13     {
14         if(d[i]>d[i-1])
15         {
16             sum+=d[i]-d[i-1];//如果后面大于前面，则共有d[i]-d[i-1]层需要单独填掉（小于的部分可以和前面一起填掉）
17         }
18     }
19     printf("%d",sum);
20     return 0;
21 }

线段覆盖（P1803）

题目描述

现在各大oj上有n个比赛，每个比赛的开始、结束的时间点是知道的。

yyy认为，参加越多的比赛，noip就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于y是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2个及以上的比赛。

输入格式

第一行是一个整数n，接下来n行每行是2个整数 a_i,b_i(a_i?<b_i?)，表示比赛开始、结束的时间。

输出格式

一个整数，表示最多参加的比赛数目。

代码

 1 #include
 2 using namespace std;
 3 const int N=1000100;
 4 int n,sum=0,now=0;
 5 struct node{
 6     int a;
 7     int b;
 8 };
 9 bool operator <(node A,node B){
10     return A.b<B.b;
11 }
12 node m[N];
13 int main(){
14     scanf("%d",&n);
15     for(int i=1;i<=n;++i)
16     {
17         scanf("%d%d",&m[i].a,&m[i].b);
18     }
19     sort(m+1,m+n+1);
20     sum=1,now=1;//选中排序后的第一个比赛
21     for(int i=2;i<=n;++i)
22     {
23         if(m[i].a>=m[now].b)//如果下一个比赛开始时间在正在参加的比赛结束时间之后（相等也可以），则选中这个比赛
24         {
25             ++sum;
26             now=i;
27         }
28     }
29     printf("%d",sum);
30     return 0;
31 }

雷达安装（P1325）

题目描述

假设海岸线是一条无限延伸的直线。它的一侧是陆地，另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上（包括海岸线），并且每个雷达都有相同的扫描范围d。你的任务是建立尽量少的雷达站，使所有小岛都在扫描范围之内。

数据使用笛卡尔坐标系，定义海岸线为x轴。在x轴上方为海洋，下方为陆地。

如图：

输入格式

第一行包括2个整数n和d，n是岛屿数目，d是雷达扫描范围。

接下来n行为岛屿坐标。

输出格式

一个整数表示最少需要的雷达数目，若不可能覆盖所有岛屿，输出-1。

代码

 1 #include
 2 using namespace std;
 3 const int N=1100;
 4 int n,d,x[N],y[N],now=0,sum=0;
 5 struct node{
 6     double L;
 7     double R;
 8 };
 9 bool operator <(node a,node b){
10     return a.R<b.R;
11 }
12 node a[N];
13 int main(){
14     scanf("%d%d",&n,&d);
15     for(int i=1;i<=n;++i)
16     {
17         scanf("%d%d",&x[i],&y[i]);
18         if(y[i]>d)//如果小岛的纵坐标比雷达的半径还要大，那么就覆盖不到这个小岛，输出-1并结束程序
19         {
20             printf("%d",-1);
21             return 0;
22         }
23         a[i].L=x[i]-sqrt(pow(d,2)-pow(y[i],2));
24         a[i].R=x[i]+sqrt(pow(d,2)-pow(y[i],2));
25         //计算出雷达可以覆盖到这个小岛的极限范围区间（用勾股定理计算，斜边为d，一个直角边为y[i]）
26     }
27     sort(a+1,a+1+n);
28     sum=1,now=1;//覆盖到第一个小岛，安放第一个雷达
29     for(int i=2;i<=n;++i)
30     {
31         if(a[i].L>a[now].R)//如果这两个区间没有公共部分，则安放下一个雷达
32         {
33             ++sum;
34             now=i;
35         }
36     }
37     printf("%d",sum);
38     return 0;
39 }