COGS 1584. [CTSC 2007]接頭辞

982 ワード

08年の论文の中の方法は半日见てとても奇怪だと感じます
アルゴリズム2いろいろ読めません.
そしてアルゴリズム1はバランスツリーを使わないようですね.
むしろアルゴリズム1のゲージを欲張りに変えて、スタックでメンテナンスすればいいです.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=200000+5;
typedef long long ll;
struct drct{
	ll c,w;
	bool operator<(const drct &rhs)const{
		return c<rhs.c;
	}
}d[N];
priority_queue<ll>q;
int main(){
	//freopen("pendant.in","r",stdin);
	//freopen("pendant.out","w",stdout);
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&d[i].c,&d[i].w);
		d[i].c+=d[i].w;
	}
	sort(d+1,d+1+n);
	ll tot=0;
	int ans=0;
	for(int i=1;i<=n;i++)
	if(d[i].c-d[i].w>=tot)q.push(d[i].w),tot+=d[i].w,ans++;
	else if(d[i].w<q.top())tot+=d[i].w-q.top(),q.pop(),q.push(d[i].w);
	printf("%d
%lld
",ans,tot); return 0; }