[数据结构与算法]贪心算法经典例题分析

贪心经典例题

一、区间覆盖问题
例题：洛谷P1803
这是一个非常简单的区间覆盖问题。
针对此类问题，最佳的贪心算法应为将每一个区间的结束时间从小到大排序。
令所选的第 i 个区间的结束时间为 e[i] ，只需从后面找到一个区间 j 使得 j 的开始时间 b[j] >= e[i] 即可（因为已经排好序了）。
这样的贪心策略也很好证明，越早结束就能有更多的时间选取更多的区间。

实现代码如下

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
int n;
struct node{
	int a,b;
}clas[maxn];
bool cmp(node x,node y)
{
	return x.b<y.b;
	if(x.b==y.b)
		return x.a<y.a;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&clas[i].a,&clas[i].b);
	sort(clas+1,clas+n+1,cmp);
	int j=1,sum=1;
	for(int i=2;i<=n;i++)
		if(clas[i].a>=clas[j].b)
		{
			sum++;
			j=i;
		}
	printf("%d",sum);
	return 0;
}

二、均分纸牌类问题
例题洛谷P1031
针对此类需要移动的问题，我们先找出平均数，再用每个数减去平均数。
那么样例数据就变成了：-1，-2，7，-4。
移动方式1：将7分向两边
移动方式2：从左向右依次移动，将-1移给-2，变为：0，-3，7，-4；
再将-3移给7变为0，0，4，-4；再将4移给-4变为0，0，0，0
易知两种策略的本质是一样的。

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,pork[105],ave,sum=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>pork[i];
		sum+=pork[i];
	}
	ave=sum/n;
	int begin=999,ans=0; //注意begin一定要附上大于n的初值
	for(int i=1;i<=n;i++)
		if(pork[i]!=ave)
		{
			begin=i;
			break;
		}
	for(int i=begin;i<=n;i++)
		if(pork[i]!=ave)
		{
			int nex=pork[i]-ave;
			pork[i+1]+=nex;
			ans++;
		}
	cout<<ans;
	return 0;
}

3、删数问题
洛谷P1106
这道题的贪心思路也比较简单，只是可能代码实现上还有点小问题。
如果要剩下的数最小，即高位的数要最小，那么只需保证越靠前的数越小即可。

代码如下（附注释）

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	string n;
	int k,num[300],ans[300];
	cin>>n;
	memset(num,0,sizeof(num));
	int len=n.length();		
	for(int i=0;i<len;i++)
		num[i]=n[i]-'0'; //为了方便转换为int
	cin>>k;
	int t=0,sit=-1,mm=k; //sit表示目前找到的位置，mm表示还需删去多少个数
	while(t<len-k)
	{
		int minn=11,ws;//ws表示找到的最小数
		for(int i=sit+1;i<=sit+1+mm&&i<len;i++)
			if(num[i]<minn)
			{
				minn=num[i];
				ws=i;
			}
		mm=mm-(ws-sit)+1;//从ws到sit的部分都删掉
		sit=ws;
		ans[t++]=minn;
	}
	bool flag=0;
	for(int i=0;i<t;i++)
	{
		if(ans[i])
			flag=1;
		if(flag==1)
			cout<<ans[i];
	}
	if(!flag) cout<<0;	//注意删去前导0
	return 0;
}

附上一道此题的进阶版洛谷P1323