学步园

这道题还是比较水的

我们稍稍推导一下

就可以得到一个贪心的算法

int rest=已花费的时间

先根据T2排序

然后i=1->n

如果这个点需要的时间+已花费时间<=目前的时间和

那么就添加

否则

比较这个点的耗时与前面选择了的点中的最大耗时

如果这个点小一些，那么就代替那个最大耗时点

否则就不取这个店

所以需要一个动态维护目前添加了的所有点的耗时

就得用到priority_queue

AC代码如下：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 150001
struct node
{
	int s;
	int t;
}p[MAX];
bool operator<(node a,node b)
{
	return a.s < b.s;
}
int n,rest = 0,ans = 0;
priority_queue<int> Q;
void init() 
{
	scanf("%d",&n);
	for (int i = 1; i <= n; i++)
		scanf("%d%d",&p[i].t,&p[i].s);
}
void work()
{
	sort(p+1,p+n+1);
	for (int i = 1; i <= n; i++)
	{
		if ( rest + p[i].t <= p[i].s )
		{
			ans++;
			rest += p[i].t;
			Q.push(p[i].t);
		}
		else
		{
			if ( !Q.empty() && p[i].t < Q.top() )
			{
				rest -= Q.top() - p[i].t;
				Q.pop();
				Q.push(p[i].t);
			}
		}
	}
	printf("%d",ans);
}
int main()
{
	init();
	work();
	return 0;
}