[TIOJ] 1231. 寵物雞問題

題目連結:http://tioj.infor.org/problems/1231
顯然最大的一定會被拿到,但是為了防止前免就拿到他,而拿不到次大的,不妨從後面開始,保證大的都會在後面才拿到,所以基本上次大的前面就會拿到,因此就有好的做法了XD
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;

int main(){
	int n,ans=0;
	scanf("%d",&n);
	vector<PII> mm;
	for(int i=0;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		mm.push_back({a,b});
	}
	sort(mm.begin(),mm.end(),[](PII a,PII b){return a.second>b.second;});
	int k,cursor=0;
	scanf("%d",&k);
	priority_queue<int> pq;
	for(int i=k;i>=1;i--){
		while(cursor<mm.size()&&mm[cursor].second>=i){
			pq.push(mm[cursor].first);
			cursor++;
		}
		if(pq.empty()){
			ans--;
		}else{
			ans+=pq.top();
			pq.pop();
		}
	}
	printf("%d",ans);
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology