简单贪心策略

贪心与证明

要选用贪心策略,就要先证明贪心策略是正确的,才能考虑使用。在很多情况下,贪心的合理性并不是显然的,但如果能找到一个反例,就可以证明这样的贪心不正确。

部分背包问题

部分背包问题
当背包问题的物品可以被任意切割的时候,贪心策略是正确的。这很好理解。只要拿单位价值最高的商品,填满袋子就是最优解。
ac代码:

#include <iostream>
#include <algorithm>
using namespace std;

int n, t;
const int N = 110;

struct Coin
{
	double v;
	double w;
	double val;
	bool operator<(const Coin& c) const
	{
		return val < c.val;
	}
}coin[N];

int main()
{
	cin >> n >> t;
	for(int i = 0; i < n; i++)
	{
		double w, v;
		cin >> w >> v;
		coin[i] = {v, w, v / w};
	} 
	sort(coin, coin + n);
	double ans = 0;
	for(int i = n - 1; i >= 0; i--)
	{
		if(t < coin[i].w)
		{
			ans += coin[i].val * t;
			t = 0;	
			break;
		} 
		else if(t > 0)
		{
			t -= coin[i].w;
			ans += coin[i].v;
		}
	}
	printf("%.2lf", ans);
}

但如何证明当背包问题物品无法被切割时,贪心策略是错误的呢?
可以用反证法,只要有一个例子可以证明贪心是错误的,那就不能用。(这个例子很好找,给的测试案例就是一个)

排队接水

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

这道题凭直觉来看也很简单。平均等待时间最小,就是让接水时间长的人少人等,即接水时间越短的人越先接水。

简单贪心策略
其实不证明也行,可以举一些例子,如果举不出反例,就证明贪心正确。可以用暴力枚举来验证答案。如果暴力和贪心答案一致,那贪心正确性很高。

ac代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

struct P
{
	int id, t;
	bool operator< (const P& p) const
	{
		if(t == p.t) return id < p.id;
		else return t < p.t;
	}
}p[N];

int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int t;
		cin >> t;
		p[i] = {i , t};
	}
	sort(p + 1, p + n + 1);
	double res = 0;
	int u = n;
	for(int i = 1; i <= n; i++)
	{
		res += p[i].t * (u - 1);
		u --;
		cout << p[i].id << ' ';
	}
	puts("");
	printf("%.2lf", res / n);
}

凌乱的yyy/线段覆盖

线段覆盖
这是一道经典的贪心问题。就是给定n个区间,最多有几个区间是不重合不相交的。

思路:从左向右看,找到结束位置最靠左的。这样可以给后面的区间更多的空间放置。在这一步上是局部最优解。然后继续找最靠左的区间,能放就放(有可能区间虽然更靠左,但是有重叠,那就不能放了)。

这样就做到了每一步都是局部最优解,那就是全局最优解了。

因此我们只要按结束位置来升序排序即可。

ac代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

struct Contest
{
	int begin, end;
	bool operator< (const Contest& c) const
	{
		return end < c.end;
	}
}contest[N];

int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		int b, e;
		cin >> b >> e;
		contest[i] = {b , e};	
	}
	sort(contest, contest + n);
	
	int ans = 0, end = -1;
	for(int i = 0; i < n; i++)
		if(contest[i].begin >= end) 
		{
			ans++;
			end = contest[i].end;
		}
	cout << ans;
}
上一篇:requests模拟请求百度翻译接口api,中文结果是Unicode,需要进行解码


下一篇:C和C++里的qsort&sort快排函数