P4053求助
查看原帖
P4053求助
201971
william_zy楼主2022/2/19 16:18
#include<bits/stdc++.h>
using namespace std;
const int N=150000+10;
typedef struct{
	int time,lim,left;
	void Node(int time=0,int lim=0,int left=0){
		this->left=left;
		this->lim=lim;
		this->time=time;
	}
}Node;
Node a[N];
int n;
class cmp1{
	public:
		bool operator()(Node a,Node b){
			return a.lim<b.lim;
		}
};
class cmp2{
	public:
		bool operator()(Node a,Node b){
			return a.time>b.time;
		}
};
priority_queue<Node,vector<Node>,cmp1> preread;
priority_queue<Node,vector<Node>,cmp2> answer;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].time>>a[i].lim;
		a[i].left=a[i].lim-a[i].time;
		preread.push(a[i]);
	}
	int sumtime=0;
	while(!preread.empty()){
		Node temp=preread.top();
		preread.pop();
		if(sumtime+temp.time>temp.lim&&!(answer.empty())&&answer.top().time>=temp.time)continue;
		if(sumtime+temp.time>temp.lim&&!(answer.empty())&&temp.time-answer.top().time<0){
			sumtime+=temp.time-answer.top().time;
			answer.pop();
			answer.push(temp);
		}else{
			answer.push(temp);
			sumtime+=temp.time;
		}
	}
	cout<<answer.size()<<endl;
}
2022/2/19 16:18
加载中...