Skip to main content

贪心

参考资料​

贪心​

贪心算法（Greedy Algorithm）是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

反悔贪心​

反悔贪心的思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

例题​

洛谷 P1209 [USACO1.3] 修理牛棚 Barn Repair

牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。所有的牛棚有相同的宽度。

自门遗失以后，Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。Farmer John 想将他购买的木板总长度减到最少。

给出 m,s,cm,s,c，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛棚所需木板的最小总长度。

Code (1)
#include <bits/stdc++.h>
using namespace std;

const int N=205;
int a[N],b[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m,s,c;
	cin>>m>>s>>c;
	for(int i=1;i<=c;i++)
	{
		cin>>a[i];
	}
	if(m>c)
	{
		cout<<c<<'\n';
		return 0;
	}
	sort(a+1,a+c+1);
	int ans=a[c]-a[1]+1;
	for(int i=2;i<=c;i++)
	{
		b[i-1]=a[i]-a[i-1];
	}
	sort(b+1,b+c+1,greater<int>());
	for(int i=1;i<=m-1;i++)
	{
		ans-=b[i]-1;
	}
	cout<<ans<<'\n';
	return 0;
}
洛谷 P1792 [国家集训队] 种树

A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。

园林部门得到指令后，初步规划出 nn 个种树的位置，顺时针编号 11 到 nn。并且每个位置都有一个美观度 AiA_i，如果在这里种树就可以得到这 AiA_i 的美观度。但由于 AA 城市土壤肥力欠佳，两棵树决不能种在相邻的位置（ii 号位置和 i+1i+1 号位置叫相邻位置。值得注意的是 11 号和 nn 号也算相邻位置）。

最终市政府给园林部门提供了 mm 棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将 mm 棵树苗全部种上，给出无解信息。

Code (1)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
struct Node
{
	int v,l,r;
}a[N];
bool vis[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].v;
	}
	if(m>n/2)
	{
		cout<<"Error!"<<'\n';
		return 0;
	}
	priority_queue<pair<int,int>> q;
	for(int i=1;i<=n;i++)
	{
		q.push({a[i].v,i});
		a[i].l=(i-2+n)%n+1;
		a[i].r=i%n+1;
	}
	ll ans=0;
	while(m)
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		ans+=a[u].v;
		m--;
		int x=a[u].l,y=a[u].r;
		vis[x]=vis[y]=1;
		a[u].l=a[x].l;a[a[x].l].r=u;
		a[u].r=a[y].r;a[a[y].r].l=u;
		a[u].v=a[x].v+a[y].v-a[u].v;
		q.push({a[u].v,u});
	}
	cout<<ans<<'\n';
	return 0;
}