这是一道很经典的贪心题

做法主要分几个步骤：

一、按照每个活动的结束时间升序。

二、每次先选在可以安排的活动中结束时间最小的，然后计算总个数。

三、输出答案。

证明：

首先，在选第一个活动的时候，如果是要选某一个活动的时候，那么那个活动肯定是挤掉的活动最少的那个，毕竟如果都被挤掉了，那还选什么？

然后，在选后面的活动的时候也是同理。

那么怎么选挤掉的活动最少的那个？

答案是选结束时间最早的那个！

然后，我们就可以轻松的解出这道题了ψ(｀∇´)ψ

AC code:

#include<bits/stdc++.h>
using namespace std;
struct dtl{
	int s,f;
}a[1001];
int n,ans=1,f;
bool cmp(dtl x,dtl y){
	return x.f<y.f;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i].s>>a[i].f;
	sort(a+1,a+1+n,cmp);
	f=a[1].f;
	for(int i=2;i<=n;++i){
		if(a[i].s<f)continue;
		ans++;
		f=a[i].f;
	}
	cout<<ans<<endl;
	return 0;
}

这是本一通上的例题。大概是橙题。

做法就是按照每个活动的结束时间升序排序，然后再贪心一遍即可。

肥波合卡游戏

#include<bits/stdc++.h>
using namespace std;
string s[50]={"glass","leaf","corn","rice","light","triangle","yucca","bone","relic","plank","basil","soil","shovel","bgg","pincer","privet","iris","powder","cactus","bubble","air","starfish","sand","sponge","lightning","claw","root","dahlia","bur","missiel","stinger","orange","wax","honey","poo","wing","faster","talisman","dice","chip","battery","sawblade","fragment","totem","mimic","corruption","crown","moon","yggdrasil","compass"},di[5]={"","legendary","mythic","ultra","super"};
map<string,int> cnt[5],p,id;
int random(int n)
{
	return 1ll*rand()*rand()%n;
}
int main()
{
	srand((unsigned)time(0));
	cout<<"you have these legendary petal:"<<endl;
	for (int i=0;i<50;i++)
		cnt[1][s[i]]=100000/*可修改，不能超过1000000*/,cout<<s[i]<<" "<<cnt[1][s[i]]<<endl;
	id["legendary"]=1;
	id["mythic"]=2;
	id["ultra"]=3;
	id["super"]=4;
	cout<<"now start to craft!"<<endl;
	while(true)//输入hxxxxxh结束合卡 
	{
		string lev,pt;
		int x,sum=0;
		cin>>lev;
		if(lev=="hxxxxxh")
			break;
		cin>>pt>>x; 
		if(cnt[id[lev]][pt]<x)
		{
			cout<<"fuck you noob宸!"<<endl;
			continue; 
		}
		x=x/5;
		for (int i=1;i<=x;i++)
		{
			int y=random(100);
			if(id[lev]==1&&y%24==0)
				sum++;
			if(id[lev]==2&&y%45==0)
				sum++;
			if(id[lev]==3&&y==50)
				sum++;
		}
		cnt[id[lev]+1][pt]+=sum;
		cnt[id[lev]][pt]=random(5);
		cout<<"you have crafted "<<sum<<" "<<di[id[lev]+1]<<" "<<pt<<"!!!!!"<<endl;
		cout<<"now you have these level "<<pt<<":"<<endl;
		for (int i=1;i<=4;i++)
			cout<<di[i]<<" "<<cnt[i][pt]<<endl;
	}
	bool flg=0;
	//legendary和mythic过于noob，所以只输出ultra和super花瓣
	cout<<"ultra petal:"<<endl;
	for (int j=0;j<50;j++)
		if(cnt[3][s[j]])
			cout<<s[j]<<" "<<cnt[3][s[j]]<<endl;
	cout<<"super petal:"<<endl;
	for (int j=0;j<50;j++)
		if(cnt[4][s[j]])
			cout<<s[j]<<" "<<cnt[4][s[j]]<<endl,flg=1;
	//出super的是pro，没出的是noob
	if(flg)
		cout<<"pro!!!"<<endl;
	else
		cout<<"noob..."<<endl;
	return 0;
}