[数据结构与算法]贪心例题汇总

1.背包问题

地址： FatMouse’ Trade

题意：有m磅猫粮n只猫，第i只猫有J[i]个Javabean需要你要用F[i]磅猫粮与它交换（可以只交换一部分），问最多能换到多少Javabean

题解：像是一个背包问题，转换为背包就是，n个物品每个物品重量为F[i],价值为J[i],放入荷重为m的背包，求最大价值。但本题因为可以只交换一部分，所以不用背包写。只需要根据J与F的比值排序，从大到小累加得答案。

代码：

#include<bits/stdc++.h>
#define maxn 1000050
#define ll long long
using namespace std;

int m,n;
struct node{
	double j,f; 
	double a;
}room[maxn];
bool cmp(node r1,node r2){//根据J与F的比值排序
	if(r1.a==r2.a) 
        return r1.f<r2.f;//比值相同则根据花费f排序
	return r1.a>r2.a;
}
void solve(){
	for(int i=1;i<=n;i++) {
		scanf("%lf %lf",&room[i].j,&room[i].f);	
		room[i].a=room[i].j/room[i].f;
	}
	sort(room+1,room+1+n,cmp);
	
	double ans=0;
	for(int i=1;i<=n;i++){
		if(m>room[i].f){
			ans += room[i].j;//累加得答案
			m -= room[i].f;//记录背包剩余重量
		}
		else{//不能全装下 则 尽可能得装
			ans += m*room[i].a;
			break;
		}
	}
	
	printf("%.3lf\n",ans);
	return ;
} 
int main(){
	while(scanf("%d %d",&m,&n)&&n!=-1&&m!=-1)
    	solve();
	return 0;
}

2.任务调度问题

地址：Schedule

题意：n个物品需要加工，第i个物品加工时间为s[i]到e[i],加工时需要用到机器，但每台机器一次只能加工一件，且一旦机器关闭就不能再打开，求最少需要开几台机器，以及开最少机器所对应的最短工作时间

题解：经典任务调度问题，可以把问题转换为求k个不重复的线段，及k段线段的总长度。
代码实现就先输入n组时间，按开始和结束分组，对2 * n个点排序，若时间相同则结束排在前。
排序后遍历2*n个点，遇到开始时间则打开一台机器，否则关闭一台；用num记录当前运行的机器数，sum记录总共开启过的机器数，每开启或关闭一个则记录下对应的时间
最后遍历所有机器，计算它们工作时间总和

代码：

#include<bits/stdc++.h>
#define maxn 100050
#define ll long long
#define pii pair<int,int>
using namespace std;

pii T[2*maxn];
int S[maxn],E[maxn];
int n,s,e;
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){//输入n组时间
		scanf("%d %d",&s,&e);
		T[2*i-1]=pii(s,1);//按开始为1 结束为0
		T[2*i]  =pii(e,0);
	}
	sort(1+T,1+T+2*n);//对2 * n个点排序
	
	memset(S,-1,sizeof(S));
	memset(E,-1,sizeof(E));
	int num=0,ans=0;//num:当前运行的机器数，sum：总共开启过的机器数 
	for(int i=1;i<=2*n;i++){
		if(T[i].second==1){//打开一台机器
			num++;
			if(S[num]==-1)
				S[num]=E[num]=T[i].first;
		
			ans=max(ans,num);
		}
		else{//关闭一台机器
			E[num]=T[i].first;
			num--;
		}
	}
	
	ll sum=0;
	for(int i=1;i<=ans;i++)//最后遍历所有机器，计算它们工作时间总和
		sum+=E[i]-S[i];
	
	printf("%d %lld\n",ans,sum);
	return ;
} 
int main(){
	int _; scanf("%d",&_);
	while(_--) solve();
	return 0;
}

3.区间调度问题

地址： Gene Assembly

题意：有n个碱基，每个碱基都有一个起始和结束位置，要求找到最多不重叠碱基组成一个DNA

题解：经典区间调度问题，思路为每次找最早结束的，这样就可以找到尽可能多的

代码：

#include<bits/stdc++.h>
#define maxn 100050
#define ll long long
#define pii pair<int,int>
using namespace std;

int n;
struct node{
	int l,r,id;
}jianji[maxn];
bool cmp(node j1,node j2){
	return j1.r<j2.r;
}
void solve(){
	for(int i=1;i<=n;i++){
		scanf("%d %d",&jianji[i].l,&jianji[i].r);
		jianji[i].id=i;
	} 
	sort(1+jianji,1+jianji+n,cmp);
	
	int preR=jianji[1].r;
	printf("%d",jianji[1].id);
	for(int i=2;i<=n;i++){
		if(jianji[i].l>preR){
			preR=jianji[i].r;
			printf(" %d",jianji[i].id);
		}
	} 
	printf("\n");
	return ;
} 
int main(){
	while(scanf("%d",&n)&&n) 
		solve();
	return 0;
}

4.简单贪心加模拟

地址： Pass-Muraille

题意：一个图上有面前

题解：当成一维思考，问题转换为删去最少的线段，使得每个点只被k条线段覆盖。局部最优：对于某个点假设被覆盖x次那么删去覆盖了它的最长的x-k面墙为最优。全局最优：从左往右找到覆盖超过k次的点，删去覆盖它的最右的的x-k面墙。实现过程中变量较多，要注意处理

代码：

#include<bits/stdc++.h>
#define maxn 100050
#define ll long long
#define pii pair<int,int>
using namespace std;

int mp[105][105];
int n,k;
void solve(){
	scanf("%d %d",&n,&k);
	int maxx=0,maxy=0;//墙的大x和y坐标
	memset(mp,0,sizeof(mp));
	for(int i=1;i<=n;i++){
		int x1,x2,y1,y2;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		if(x1>x2) swap(x1,x2);
		maxx=max(maxx,x2);//维护最大坐标
		maxy=max(maxy,y1);
		for(int j=x1;j<=x2;j++) mp[j][y1]=i;//记录第i面墙
	}
	
	int ans=0;
	for(int i=0;i<=maxx;i++){//从左往右找 
		int num=0;//记录被覆盖的次数
		for(int j=0;j<=maxy;j++)//从上往下找 
			if(mp[i][j]>0) num++;
		
		num-=k;//此时num为需要删除的墙的数量
		if(num>0){
			ans+=num;
			while(num--){//每次去找最右的墙
				int maxt=0,maxid=0;
				for(int y=0;y<=maxy;y++){//从上往下找
					if(mp[i][y]>0){
						int t=0; 
						for(int x=i+1;x<=maxx;x++){//从左往右找 
							if(mp[x][y]==mp[i][y]) t++;
							else break;
						} 
                        //记录当前最远的一面墙
						if(t>maxt) maxt=t,maxid=y;
					}
				}
				for(int x=i;x<=i+maxt;x++)//删去最远的一面墙
					mp[x][maxid]=0;
			}
		}
	}
	
	printf("%d\n",ans);
	return ;
} 
int main(){
	int _;cin>>_;
	while(_--) 
		solve();
	return 0;
}

5.多解贪心

地址： Tian Ji – The Horse Racing

题意：模拟田忌赛马，计算田忌最多能赢几次

题解：分情况讨论
田忌最慢 > 齐王最慢 ：田忌最慢 对战 齐王最慢 赢
田忌最慢 < 齐王最慢 ：田忌最慢 对战 齐王最快 输
田忌最慢 = 齐王最慢 ：
田忌最快 > 齐王最快：田忌最快 对战 齐王最快 赢
田忌最快 ≤ 齐王最快：
田忌最慢 < 齐王最快 ：田忌最慢 对战 齐王最快 输
田忌最慢 = 齐王最快：田忌最慢 对战 齐王最快 平

代码：

#include<bits/stdc++.h>
#define maxn 100050
#define ll long long
#define pii pair<int,int>
using namespace std;

int n;
int qw[maxn],tj[maxn];
void solve(){
	for(int i=1;i<=n;i++) scanf("%d",&tj[i]);
	for(int i=1;i<=n;i++) scanf("%d",&qw[i]);
	sort(1+tj,1+tj+n);
	sort(1+qw,1+qw+n);
	
	int sum=0;
	int tl=1,ql=1,tr=n,qr=n;
	while(tl<=tr){
		if(tj[tl]>qw[ql])//田忌最慢 > 齐王最慢 
			ql++,tl++,sum+=200;
		else if(tj[tl]<qw[ql]) //田忌最慢 < 齐王最慢 
			qr--,tl++,sum-=200;
		else{//田忌最慢 = 齐王最慢 
			if(tj[tr]>qw[qr])//田忌最快 > 齐王最快 
				qr--,tr--,sum+=200;
			else {//田忌最快 <= 齐王最快 
				if(tj[tl]<qw[qr]) //田忌最慢 < 齐王最快 
					sum-=200;
				tl++,qr--;
			}
		}
	}
	
	printf("%d\n",sum);
	return ;
} 
int main(){
	while(scanf("%d",&n)&&n) 
		solve();
	return 0;
}