给初学者的——贪心算法（上）

引入

首先，我们先来看到一道例题，来引入贪心算法的学习。

最大乘积——例题引入

运用贪心算法解决问题，就需要我们找到一种一以贯之的策略，这种策略就叫做贪心策略，这种策略能保证取得最优。也就是说，贪心算法就是在每一步操作中，都选择局部最优解（当然，你需要保证这样取能得到全局最优解）。

所以说，我们解决这一类问题，目标便是找到贪心策略。一般地，我们需要发现、挖掘性质得出最优解。

首先，非常显然地，如果n ≤ 4，那么直接输出n即可。对于n ≥ 5，首先为了乘积最大，是不可能拆出1来的（非常显然），又要为了乘积最大，所以拆出来的数就必须要多，所以说不难想出，最后的形式一定是2 + 3 + 4 + ... + (m - 1) + m + r，其中r ≤ m + 1。如果r = m + 1，直接输出即可，但是如果r < m + 1，就会出现重复，根据我们小学二年级就学过的“和一定，差小积大”，我们需要把r分配给m - r + 1到m的所有数，每个数分配1。（读者可以把1到10都试一遍，猜出策略）

这就是这道题的贪心策略（其实是非常简单的）。

下面，上代码！！！

ac代码

#include <iostream>
#include <algorithm> //为了用exit()函数 
using namespace std;
int n;
int main() {
	ios::sync_with_stdio(false), cin.tie(null);//给程序提提速 
    int tmp = 0, border;//临时变量，边界 
    cin >> n; 
    if (n <= 4) {//特判 
        cout << n;
        exit(0);//game over 
    }
    for (int i = 2;; i++) {
        tmp += i;
        if (tmp > n) {
            border = i - 1;//寻找边界，即什么时候这一串数的连续性被打断，出现重复 
            break;
        }
    }
    int tmp1 = n - ((border + 2) * (border - 1) / 2);
    int border1 = border - tmp1;//多少个数可以正常输出（即形如2 3 ... 2 + border1 - 1） 
    if (border1 == 0) {//特判 
        for (int i = 3; i <= border; i++)
			cout << i << ' ';
        cout << border + 2;
        exit(0);//game over 
    }
    for (int i = 2; i <= border1; i++) 
		cout << i << ' ';
    for (int i = border1 + 1; i <= border; i++)
		cout << i + 1 << ' ';
    return 0;//功德圆满 
}

小结

贪心算法的目标是找到某个“一以贯之的策略”；

从小到大分析，或逐个元素分析，往往会得到有用的结论；

把结论联合起来，能得到最终的策略。

几道有趣的例题

纸牌游戏

思路

首先，我们先要明确什么时候无法达成目标的两种局面。经过屏幕前的你两秒半的思考后，大概就会发现，当这n个数的和与1 + 2 + ... + n的和不相等时，那么无论怎么操作，都是达成不了的，所以直接输出-1即可。

那么，在去掉这种特殊情况后，我们就要去寻找这道题的贪心策略，而这道题的贪心策略也应该是比较好找的。请屏幕前的你自行思考两分半。。。

很好，相信在你的细心观察与思考下，不到两分半就找到了这道题的正确解法。

在样例解释的提醒下，真正的贪心策略如下：首先看升序情况，从后往前（其实从前往后也行，主要看你自己）依次判断第i个数是否等于i，如果是，就判断下一个数，如果不是，就把这个数变成i（就是加一个数tmp），那么下一个被判断的数就要减去这个数tmp，然后总操作数再加1，以此类推。。。这种情况模拟完之后，再同理模拟降序情况即可。

ok！！！这道题就基本做完了！！！

下面，上代码！！！（这份代码应该是最快的，不信你看）

ac代码

#include <iostream>
#include <algorithm>
using namespace std;
const int n = 1e6 + 11;
int n, a[n], b[n], ans1, ans2;
int main(){
	ios::sync_with_stdio(false), cin.tie(null);//给程序提提速 
	cin >> n;
	int sum = 0;//标记总和
	for(int i = 1; i <= n; i++){
		cin >> a[i]; //读入，作为第一种升序情况
		sum += a[i];//总和加上a[i]
		b[i] = a[i];//额外记录第二种降序情况
	}
	if(n * (n + 1) != sum * 2){//用我们幼儿园就学过的知识判断总和
		cout << "-1" << '\n';
		exit(0);//game over
	}
	for(int i = n; i >= 2; i--){//升序
		if(a[i] != i){
			int ikun = a[i] - i;
			a[i - 1] += ikun;//模拟一次操作
			ans1++; 
		}
	}
	for(int i = n; i >= 2; i--){//降序
		if(b[i] != n + 1 - i){
			int ikun = b[i] - n - 1 + i;
			b[i - 1] += ikun;//模拟一次操作
			ans2++;
		}
	}
	int ans = (ans1 < ans2) ? ans1 : ans2;//得到两种情况的最小值
	cout << ans << '\n';//输出
	return 0;//功德圆满：）
}

上面这道题其实很简单，相信对你没有什么挑战性。

那么我们接着看这道题（相信普通的过河问题对你来说太简单了）

过河问题2.0

这道题还是很有难度的（不信你看↓）

（最左侧表示人数，下侧表示大于等于该分数的一共有多少人（366人惨烈牺牲））

但是

相信屏幕前聪明的你一定能做出来！！！

思考片刻，拿起纸和笔，算一算吧！（核善...和善的微笑）

思路

首先，我们需要对所有时间ti按照升序做排序处理（比较显然，不再赘述）：t1 ≤ t1 ≤ ... ≤ tn

基本推论

推论一

推论二

推论三

详细分析

直观分析

数学分析

#include <iostream>
#include <algorithm>
using namespace std;
const int n = 2011;
int n, t[n], ikun;
int main(){
	ios::sync_with_stdio(false), cin.tie(null);
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> t[i];
	sort(t + 1, t + 1 + n);
	int border = 0;
	for(int i = n; i >= 1; i--){
		if(4 * t[2] > t[1] + t[i]){
			border = i;
			break;
		}
	}
	if(2 * border - 1 >= n){
		if(n % 2 == 0 && t[1] + t[n / 2 + 1] > 2 * t[2]){
			ikun += 2 * t[2];
			n--;
		}
		for(int i = 2; i <= n / 2 + 1; i++)
			ikun += t[1] + t[i];
		ikun -= t[1];
	} else {
		ikun += 2 * t[2] * (n - (2 * border - 1));
		for(int i = 2; i <= border; i++)
			ikun += t[1] + t[i];
		ikun -= t[1];
	}
	cout << ikun << '\n';
	return 0;
}

#include <iostream>
#include <algorithm>
#include <iomanip>//为了用fixed与setprecision()函数
using namespace std;
int k, w, s, aa, bb;
struct metal {
    int weight;
    int value;
} a[3005];
bool cmp(metal x, metal y){ 
	return x.value * y.weight > y.value * x.weight; //按照性价比升序排列（交叉相乘得到）
}
int main() {
    ios::sync_with_stdio(false), cin.tie(null);
    cin >> s >> w;
    for (int i = 1; i <= s; i++)
        cin >> a[i].weight;
    for (int i = 1; i <= s; i++)
        cin >> a[i].value;
    cin >> aa >> bb;
    int t = w - aa;
    sort(a + 1, a + s + 1, cmp);
    double ans = 0, ans1 = bb;
    for (int i = 1; i <= s; i++) {//不含宝石
        if (w >= a[i].weight) {
            ans += a[i].value;
            w -= a[i].weight;
        } else {
            ans += w * (1.0 * a[i].value / a[i].weight);
            break;
        }
    }
    for (int i = 1; i <= s; i++) {//含宝石（“算两次”）
        if (t >= a[i].weight) {
            ans1 += a[i].value;
            t -= a[i].weight;
        } else {
            ans1 += t * (1.0 * a[i].value / a[i].weight);
            break;
        }
    }
    cout << fixed << setprecision(3) << max(ans, ans1) << endl;//四舍五入保留三位
    return 0;//功德圆满
}

思路

我们将1,2,3, … 𝑖 − 1, 𝑖, 𝑖 + 1, 𝑖 + 2, … , 𝑛变为1,2,3, 𝑖 − 1, 𝑖 + 1, 𝑖, 𝑖 + 2, … , 𝑛。交换前后，[1. . 𝑖 − 1] 和 [𝑖 + 1. . 𝑛] 这两个区间里面的所有编号的同学的暴躁程度不变。

也就是说，我们交换𝑖和𝑖 + 1两位同学，只影响交换的这两个，此时我们可以考虑使用临项交换法（这道题你可以认为是搭积木，排队接水这一类题的一个变式）。

首先，我们还是需要找到排序的参数。于是，我们又得经过一大堆繁琐的数学推导（其实也没有太繁琐）。仿照上面那一道堆积木的题，我们可以得到过程基本如下：

考虑交换前𝑖和𝑖 + 1的暴躁程度：

• g𝑖 = t0 + t1 + ... + ti-1 - pi + ci+1 + ci+2 + ... + cn-1
• g𝑖+1 = t0 + t1 + ... + ti-1 + ti - pi+1 + ci+2 + ... + cn-1

再考虑交换后𝑖和𝑖 + 1的暴躁程度：

• h𝑖+1 = t0 + t1 + ... + ti-1 - pi+1 + ci + ci+2 + ... + cn-1
• h𝑖 = t0 + t1 + ... + ti-1 + ti+1 - pi  + ci+2 + ... + cn-1

这一坨k = t0 + t1 + ... + ti-1 + ci+2 + ... + cn-1是所有项共有的，那么我们有：

• g𝑖 = k − pi + ci+1.
• g𝑖+1 = k + t𝑖 − p𝑖+1.
• h𝑖+1 = k − p𝑖+1 + ci.
• h𝑖 = k + t𝑖+1 − p𝑖

接下来，我们考虑  max{h𝑖 , h𝑖+1} < max{g𝑖 , g𝑖+1}，即max{ti+1 - pi, -pi+1 + ci} < max{-pi + ci+1, ti - pi+1}（这里取不取等其实是无所谓的，只要这样操作不变差就行）。

我们先来看右边的最大值。如果是ti - pi+1，因为题目中已经说过ti ≤ ci，所以-pi+1 + ci ≥ ti - pi+1，那么左边的最大值只能是ti+1 - pi。那么我们可以推出ti+1 - pi < ti - pi+1，也就是ti+1 + pi+1 < ti + pi。在此基础上，又因为我们假设ti - pi+1是右边的最大值，即ti - pi+1 > -pi + ci+1，且-pi + ci+1 ≥ -pi + ti+1，那么ti - pi+1 > -pi + ti+1，ti + pi > ti+1 + pi+1，与前面矛盾！

所以说，右边的最大值只能是-pi + ci+1，也就是说，-pi + ci+1 > ti - pi+1，如果左边的最大值是ti+1 - pi的话，是显然成立的，它一定小于（等于）左边，那么我们再考虑-pi+1 + ci。于是，我们便得到了-pi+1 + ci < -pi + ci+1，移项得pi + ci < pi+1 + ci+1。

终于，在历经千辛万苦之后，我们得到了这么一串式子。于是乎，我们便可以知道这道题需要我们按照pi + ci升序排序，然后再从0号学生开始依次进行操作。

ok，最主要的部分已经讲完了，相信下面的部分一定难不倒大家。

上代码！！！

ac代码

#include <iostream>
using namespace std;
struct stu{
	int t, p, c;//定义结构体
}ikun[3011];
int n;
void qswap(int x, int y){
	stu akun = ikun[x];
	ikun[x] = ikun[y];
	ikun[y] = akun;
}//交换结构体函数
int main(){
	ios::sync_with_stdio(false), cin.tie(null);//给程序提提速
	cin >> n;
	for(int i = 1; i <= n; i++)//作者本人还是习惯从1开始读入
		cin >> ikun[i].t >> ikun[i].p >> ikun[i].c;//读入
	bool flag1 = true;//特判，如果全是0那么跳过排序
	for(int i = 1; i <= n; i++){
		if(ikun[i].t != 0 || ikun[i].c != 0)
			flag1 = false;
	}
	if(flag1)
		goto flag;//跳过排序
	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++){
			if(ikun[i].c + ikun[i].p < ikun[j].c + ikun[j].p)//对pi + ci进行升序排序
				qswap(i, j);
		}
	flag: int ckun = 0;
	for(int i = 3; i <= n; i++)
		ckun += ikun[i].c;
	int ans = -ikun[1].p + ckun + ikun[2].c, tkun = ikun[1].t;
	for(int i = 2; i <= n; i++){
		ans = max(ans, tkun - ikun[i].p + ckun);
		tkun += ikun[i].t;
		ckun -= ikun[i + 1].c;
	}//操作部分，不再赘述
	cout << ans;
	return 0;//功德圆满
}

总结

那么，以上就是本篇文章的全部内容。每一道例题的方法都不唯一，作者的方法也不一定是最快的，如果读者有兴趣，可以自行探索其它方法！这是作者本人在csdn博客上的第一篇文章，希望大家能够多多点赞，收藏，支持一下！！！谢谢大家！！！

（作者本人还是萌新，有没有大佬教一教latex的使用，感激不尽！！！）

完结撒花！！！

特别鸣谢

jx.7fa4.cn:8888