求助贪心
  • 板块灌水区
  • 楼主wo_hen_la
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/11/4 12:32
  • 上次更新2023/11/4 14:42:11
查看原帖
求助贪心
794701
wo_hen_la楼主2023/11/4 12:32

P4053 思路好像没问题

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct node
{
	long long t1,t2;
}a[150005];
bool cmp(node x,node y)
{
	return x.t1<y.t1;
}
priority_queue<long long,vector<long long>,greater<long long> > r;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].t1>>a[i].t2;
	}
	sort(a+1,a+1+n,cmp);
	long long tim=0,ans=0;
	for(int i=1;i<=n;i++){
		if(tim+a[i].t1<=a[i].t2){
			tim+=a[i].t1;
			ans++;
			r.push(a[i].t1);
		}
		else if(r.top()>a[i].t1){
			if(tim-r.top()+a[i].t1<=a[i].t2){
				tim-=r.top();
				r.pop();
				r.push(a[i].t1);
				tim+=a[i].t1;
			}
		}
	}
	cout<<r.size();
	return 0;
}
2023/11/4 12:32
加载中...