反悔贪心求助
查看原帖
反悔贪心求助
713562
hahaxiang楼主2023/3/25 19:34

这是之前的写法70pts

#include<bits/stdc++.h>
using namespace std;
const int N=150000+100;
struct build{
	int t1,t2;
}a[N]; 
int n;
bool cmp(build x,build y)
{
	return x.t2<y.t2;
}
long long sum,num;
priority_queue<int,vector<int>,less<int> >q;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i].t1>>a[i].t2;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(sum+a[i].t1>a[i].t2)
		{
			if(q.size()!=0)
			{
				if(sum-q.top()+a[i].t1<=a[i].t2)
				{
					sum-=q.top();
					sum+=a[i].t1;
					q.pop();
					q.push(a[i].t1);
				}
			}
		}
		else
		{
			sum+=a[i].t1;
			num++;
			q.push(a[i].t1);
		}
	}
	cout<<num;
	return 0;
}

这是之后的写法100pts:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=150000+100;
struct build{
	int t1,t2;
}a[N]; 
int n;
bool cmp(build x,build y)
{
	return x.t2<y.t2;
}
int sum,num;
priority_queue<int,vector<int>,less<int> >q;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i].t1>>a[i].t2;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		sum+=a[i].t1;
		q.push(a[i].t1);
		if(sum<=a[i].t2)
		num++;
		else
		{
			sum-=q.top();
			q.pop();
		} 
	}
	cout<<num;
	return 0;
}

求助区别在哪里?

2023/3/25 19:34
加载中...