COGS 1584. [CTSC 2007]接頭辞
982 ワード
08年の论文の中の方法は半日见てとても奇怪だと感じます
アルゴリズム2いろいろ読めません.
そしてアルゴリズム1はバランスツリーを使わないようですね.
むしろアルゴリズム1のゲージを欲張りに変えて、スタックでメンテナンスすればいいです.
アルゴリズム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;
}