小Y做比赛

小Y正在和大家一起参加比赛，比赛共有N道题目，比赛规则是根据做出题目数量来确定排名的，当出题数相同则罚时少的排名在前，一位参赛选手罚时等于他每道做出的题目的罚时之和，做一道题目的罚时等于做出该题目时距离比赛开始后的时间，另外每次错误的提交也会增加罚时。

小Y很厉害，他能做出所有的N道题目，并且不会有提交错误。而对于每道题目，他需要花费一定的读题时间和做题时间，当然他需要读过一道题才能去做那道题。

小Y有一个做题习惯，就是仅当他有两道读过并且还没做出的题时，他才会去做题，并且会选择去做花费做题时间较少的那题。除了只剩一题的情况下，他会去把那题做完。

现在已知这些题目对于小Y的读题时间和做题时间，而小Y的读题顺序是任意的，求小Y最少可能的罚时。（假设小Y在任何情况下都会在比赛时间内做完所有题）

#include<bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef long long ll; const int N=1e5+5; int a[N],b[N]; P c[N],d[N]; bool vis[N]; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&a[i],&b[i]); c[i]=P(a[i]+b[i],i); d[i]=P(a[i],i); } sort(c,c+n); sort(d,d+n); ll ans=(ll)d[0].first*n; int last=b[d[0].second]; vis[d[0].second]=1; int p1=0,p2=0; for(int i=0;i<n-1;i++) { while(p1<n&&vis[c[p1].second]) p1++; while(p2<n&&vis[d[p2].second]) p2++; int t1=a[c[p1].second]+min(last,b[c[p1].second]); int t2=a[d[p2].second]+min(last,b[d[p2].second]); int p; if(t1<=t2) p=c[p1].second; else p=d[p2].second; vis[p]=1; ans+=(ll)(n-i)*(min(t1,t2)); last=max(last,b[p]); } ans+=last; printf("%lld\n",ans); return 0; }

详情