2013-team5/andrew/30/G

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> PLL;
const int INF=1e8, MN=1e6+7;
int n,m;
PLL a[MN];

int main(){
    freopen("pulp.in","r",stdin);
    freopen("pulp.out","w",stdout);

    scanf("%d",&n);
    int i,j,k;
    for (i=1; i<=n; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]=PLL(x,y);
    }
    sort(a+1,a+n+1);
    priority_queue <LL, vector<LL>, greater<LL> > Q;
    LL ans=0;
    LL time,now,pre=0;
    i=1;
    while (i<=n){
        now=a[i].first;
        if (!Q.empty()){
            time=Q.top(); Q.pop();
            while (now-pre>=time){
                pre+=time;
                ans+=pre;
                time=0;
                if (!Q.empty()) { time=Q.top(); Q.pop(); }
                else break;
            }
            if (time>0) Q.push(time-(now-pre));
        }
        while (i<=n && a[i].first<=now) Q.push(a[i++].second);
        pre=now;
    }
    while (!Q.empty()){
        now+=Q.top();
        ans+=now;
        Q.pop();
    }
    printf("%I64d\n",ans);
  //  cout << ans << endl;
    return 0;
}
}}}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> PLL;
const int INF=1e8, MN=1e6+7;
int n,m;
PLL a[MN];
int main(){
    freopen("pulp.in","r",stdin);
    freopen("pulp.out","w",stdout);
    scanf("%d",&n);
    int i,j,k;
    for (i=1; i<=n; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]=PLL(x,y);
    }
    sort(a+1,a+n+1);
    priority_queue <LL, vector<LL>, greater<LL> > Q;
    LL ans=0;
    LL time,now,pre=0;
    i=1;
    while (i<=n){
        now=a[i].first;
        if (!Q.empty()){
            time=Q.top(); Q.pop();
            while (now-pre>=time){
                pre+=time;
                ans+=pre;
                time=0;
                if (!Q.empty()) { time=Q.top(); Q.pop(); }
                else break;
            }
            if (time>0) Q.push(time-(now-pre));
        }
        while (i<=n && a[i].first<=now) Q.push(a[i++].second);
        pre=now;
    }
    while (!Q.empty()){
        now+=Q.top();
        ans+=now;
        Q.pop();
    }
    printf("%I64d\n",ans);
  //  cout << ans << endl;
    return 0;
}