【C++天梯计划】1.3 贪心算法(greedy algorithm)

🎆🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎆
今天我要开启一个新计划----【C++天梯计划】
目的是通过天梯计划，通过题目和知识点串联的方式，完成C++复习与巩固。

什么是贪心?

贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

算法思路

贪心算法一般按如下步骤进行：
①建立数学模型来描述问题 。
②把求解的问题分成若干个子问题 。
③对每个子问题求解，得到子问题的局部最优解 。
④把子问题的解局部最优解合成原来解问题的一个解 。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。

例题1：排队打水问题

题目描述

有 nn 个人排队到 rr 个水龙头去打水，他们装满水桶的时间 t_1,t_2,…,t_nt 1​ ,t 2 ,…,t n​
为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的总时间最少？
每个人打水的时间 = 排队的时间 + 实际打水的时间，本题假设一个人打好水，排在他后面的人接着打水的这个切换过程不消耗时间。
比如，有 22 个人 AA 和 BB ，他们打水的时间分别是 33 和 22 ，只有 11 个水龙头，这时，如果 AA 先打水，BB 后打水，那么 AA 和 BB 打水的时间分别为 33 、3+23+2（ BB 排队 33 分钟）。
因此，所有人打水的总时间就是每个人的打水时间及每个人的排队时间的总和。

输入

第 11 行，两个整数 nn(1≤n≤5001≤n≤500)和rr(1≤r≤1001≤r≤100)。
第 22 行，nn个正整数 t_1,t_2,…,t_nt 1 ,t 2​ ,…,tn ，(1≤t_i≤10001≤t i ≤1000)表示每个人装满水桶的时间。

输出

11 行，一个正整数，表示他们花费的最少总时间。

样例

输入
4 2
2 6 4 5
输出
23

思路

每个人的总打水时间 = 该用户打水时间 + 排队等待时间，因此只有打水快的人先打，总的排队时间才是最少的。

代码：

#include
using namespace std;
int n,a[510],r,i,s = 0;
int main(){	
	 cin>>n>>r;
	 //读入每个人的打水时间 
	 for(i = 1;i <= n;i++)
	 	cin>>a[i];
	 //排序:从小到大，打的快的先打 
	 sort(a+1,a+n+1); 
	 //从第r+1个人开始修正每个人的总打水时间
	 //求和
	 for(i = 1;i <= n;i++){
	 	if(i >= r + 1) a[i] += a[i-r]; //相当于a[i]=a[i]+a[i-r]; 
	 	s = s + a[i];
	 } 	 
	 cout<<s;	  
	 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

例题2：

题目描述

在一个月黑风高的暴风雨夜，Farmer John 的牛棚的屋顶、门被吹飞了好在许多牛正在度假，所以牛棚没有住满。
牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。
自门遗失以后，Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。 Farmer John 想将他购买的木板总长度减到最少。
给出 m,s,cm,s,c，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛棚所需木板的最小总长度。

输入

一行三个整数 m,s,cm,s,c ，意义如题目描述。
接下来 cc 行，每行包含一个整数，表示牛所占的牛棚的编号，牛棚编号不保证有序。
数据范围
对于 100%100% 的数据，1≤m≤501≤m≤50，1≤c≤s≤2001≤c≤s≤200。

输出

输出一行一个整数，表示所需木板的最小总长度。

样例

输入
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43
输出
25

思路

假设m = 1，也就是有1块木板，那么这块木板必须从1到10封住所有位置，才能把所有牛都挡起来，则答案 = 10 - 1 + 1 = 10。
假设m = 2，也就是有2块木板，那么从4-z9之间的木板就可以拆除，仅需要：1-3位置放一块木板，以及10的位置放一块木板，则答案 = 3 + 1 = 4。
假设m = 3，也就是有3块木板，可以继续将2位置的木板拆除，每头牛都可以单独设置一块木板，则答案= 1 + 1 + 1 = 3。
通过分析发现，如果m >= c，每头牛都可以单独设置一块木板，答案一定是c。如果m < c，则可以拆出m - 1个空隙，因此可以通过贪心的思想，从最大的空隙开始拆除，直到我们拆出m - 1个空隙。

代码：

#include
using namespace std;
int m,s,c,ans;
int a[210],b[210];
int main(){
    //m块板子，s个牛棚，c头牛
    cin>>m>>s>>c;
    //读入c头牛的位置
    for (int i = 1; i <= c; i++)
    {
        cin>>a[i];
    }

    //特殊情况，如果板子比牛多，每头牛可以安排一个板子
    if(m >= c){
        cout<<c;
        return 0;
    }

    //对牛的位置排序，输入可能无序
    sort(a + 1,a + c + 1);

    //特殊情况：1块板子就够的情况
    ans = a[c] - a[1] + 1;
    //求第i个位置的牛棚，距离第i+1个位置的牛棚的间隔
    for (int i = 1; i <= c - 1; i++)
    {
        b[i] = a[i + 1] - a[i] - 1;
    }

    //对间隔升序
    sort(b + 1,b + c);
    //逆序从最大间隔开始拆
    for (int i = c - 1; i >= c - m + 1; i--)
    {
        ans = ans - b[i];
    }

    cout<<ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40