贪心算法(c++)

一、贪心算法介绍

基本原理：每一步都选择局部最优解，而尽量不考虑对后续的影响，最终达到全局最优解。

局限性：贪心算法不能保证获得全局最优解，但在某些问题上具有高效性。

特征：贪心选择性质、最优子结构性质(根据我的观察，很多贪心的题目会出现“不同的操作产生的贡献相同”的特征，在此特征下我们每次选择代价最小的。)

贪心类型多且杂，需要积累联系。

二、贪心算法实现步骤

1、确定问题的最优子结构（贪心往往跟排序、优先队列等一起出现）。

2、构建贪心选择的策略，可能通过“分类讨论”、“最小代价”、“最大价值”等方式来思考贪心策略。简单验证贪心的正确性，采用句式一般是：这样做一定不会使得结果变差、不存在比当前方案更好的方案等等。

3、通过贪心选择逐步求解问题，直到得到最终解。

三、例题

1、蓝桥OJ3412 最小化战斗力差距

https://www.lanqiao.cn/problems/3412/learning/?page=1&first_category_id=1&problem_id=3412

思路：

简单排序模型。

要将战斗力分为两部分，假设有一个a数组，一个b数组。将战斗力排序后进行划分，左边的在a数组中，右边的在b数组中，a数组的最后一个和b数组第一个元素的差距即战斗力差距，其他元素都可以忽略，故枚举即可。找间隙最小。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 9;

int a[N];

int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+1+n);
	int ans = a[2] - a[1];
	for (int i = 1; i < n; i++) ans = min(ans,a[i+1]-a[i]);//有i+1故<n 
	cout << ans << '\n';
} 

体会：

当遇到元素混乱的问题时，可以试着把元素排序，当然是在不影响题目的情况下。 

2、蓝桥OJ545 谈判

https://www.lanqiao.cn/problems/545/learning/?page=1&first_category_id=1&problem_id=545

思路：

这是一个总操作数一定情况下的“最小代价”问题。

我们要实现花费最少的金币，贪心地想，假如我们每次把人数最少的两个部落加起来，是不是就可以实现花费的金币最少呢，即每次选择代价最小的两个部落合并。

我们可以采用优先队列，按greater排序，就可以使top变成最小的值(小根堆)，取上面两个最小的值相加并pop出队列，再push两个最小的值相加的值进入队列，最后累加出结果即为最小花费。

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
priority_queue<ll,vector<ll>,greater<ll>> pq;

int main()
{
	int n;cin >> n;
	ll m;
	for (int i = 1; i <= n; i++)
	{
		cin >> m;
		pq.push(m);
	}
	ll ans = 0;
	while(pq.size() > 1)
	{
		ll x = pq.top(); pq.pop();
		ll y = pq.top(); pq.pop();
		
		ans += x + y;
		
		pq.push(x+y);
	}
	cout << ans <<'\n';
	return 0;
} 

3、蓝桥OJ532 纪念品分组

https://www.lanqiao.cn/problems/532/learning/?page=1&first_category_id=1&problem_id=532

思路：

这是一个最少数目的贪心模型。

题目要求每组纪念品价格之和不能超过给定的整数，且每组最多只能两件纪念品。并分组数目最少。我的贪心策略就是，最贵带最便宜的成为一组。若装不下就单独成为一组。

采用二分的思想，将l=1，r=n，左(小)右(大)同时遍历数组，若找到一组就l++,r–,且组数+1，若没找到则说明溢出了，r–，单独成为一组组数也要+1，最后判断l=r，代表遍历完成break结束。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 9;
int a[N];

int main()
{
	int w, n; cin >> w >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+1+n);
	int l = 1, r = n, ans = 0;
	while(l <= r)
	{
		ans++;
		if (l == r) break;
		if (a[l] + a[r] <= w)
		{
			r--;
			l++;
		} 
		else r--;
	}
	cout << ans << '\n';
	return 0;
} 

4、蓝桥OJ2928 分糖果

https://www.lanqiao.cn/problems/2928/learning/?page=1&first_category_id=1&problem_id=2928

这是一个找规律的贪心模型。

题目要求我们使所有糖果组成的字符串中字典序最大的字符串尽可能小。需要我们分三种情况：

（1）当字符串全部相等时(假设为aaaaaaa)，要把这7个a分给3个同学，那么分为(aa)(aa)(aaa)即是最优，所以此情况，我们只需要使每个人分到的字符串的最大长度尽可能小。

（2）当s[x] == s[1]，说明第x个是最小的字符串，带着后面所有的字符一起输出。

（3）当s[x] != s[1]，后面的字符可以直接丢到s[1]后面，分给第一个同学。那么x个同学肯定就是字典序最大的了。(假设w=5,x=2,s=”abbcd”)，我们将后面的bcd丢给第一个同学，abcd的字典序<b的字典序。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 9;
char s[N];

int main()
{
	int n, x; cin >> n >> x;
	cin >> s + 1;
	sort(s+1,s+1+n);
	
	if (s[1] == s[n])//字符串全相等
	{
		for (int i = 1; i <= n / x + (n % x ? 1 : 0); ++i) cout << s[i];
	} 
	else if (s[1] == s[x])
	{
		for (int i = x; i <= n; ++i) cout << s[i];
	}
	else	cout << s[x];
	return 0;
}

贪心题目的类型多而杂，需要自己不断积累。欢迎大家指正。