cls与lzp的热身赛

发布时间: 2017年12月11日 13:58   最后更新: 2017年12月11日 14:46   时间限制: 1000ms   内存限制: 128M

描述

众所周知，长春理工大学的“嗨呀好气啊”队伍由两个菜鸡lzp和cls以及某X姓巨巨组成，热身赛打的太好可能导致电脑里的PC^2被删掉，所以热身赛一般都是由lzp和cls两个菜鸡代表队伍参加比赛，热身赛由n道题组成，他们队内分工明确，lzp想出思路，然后cls去写，第i个题目lzp思考出来的是第ai分钟，cls需要bi分钟来写（显然需要lzp想出思路cls才能去写这个题目），由于cls比较优秀，cls可以在写一道题的中途换写另一道题（cls写正在写A题时，可以跳去写B题，然后再回来写A题，也可以去写C题），设第i道题在第ci分钟写完，那么最后得到的罚时就是Σci（ci的和）。

lzp和cls当然希望他们的罚时最少（即Σci最小），快来帮帮他们吧！

输入

多组输入，每组第一行输入一个数n(0<n<100000),

接下来的n行每行输入两个数ai和bi，分别表示第i个题lzp需要思考的时间和cls需要写的时间(0<ai,bi<100)。

输出

每组输出一个数x，表示lzp和cls解决n道题的最少罚时。

样例输入1

31 52 13 721 73 6

样例输出1

2422 题目分析 ： 题意还是很好理解的，很明确，想一想会发现，就是你不管怎么去换题目，你敲完最后一道题目的时间是确定的，那么就课以想到一个贪心策略，尽可能早的完成题目，以减少罚时，这里可以用优先队列去维护，当在a[i]时间的时候，你可以操作的时间就是到a[i+1]，在这个时间内，你要去完成这段时间可以完成的题目。自己理会一下吧！ 代码示例 ：  注意是 long long 　　

struct node{    ll a, b;        bool operator< (const node &c)const{        return a < c.a;    }}pre[eps];priority_queue
      
       , greater
       
         >que;int main() {    //freopen("in.txt", "r", stdin);    //freopen("out.txt", "w", stdout);    int n;        while(~scanf("%d", &n)){        for(int i = 1; i <= n; i++){            scanf("%lld%lld", &pre[i].a, &pre[i].b);        }        sort(pre+1, pre+1+n);        ll ans = 0;        ll t;        for(int i = 1; i <= n; i++){            t = pre[i].a;            ll u = pre[i].b;            que.push(u);                        if (i < n){                while(!que.empty()){                    if (t >= pre[i+1].a) break;                                        u = que.top();                    que.pop();                                        if (t + u <= pre[i+1].a){                        t += u;                        ans += t;                          }                    else {                        u -= pre[i+1].a - pre[i].a;                        t = pre[i+1].a;                        que.push(u);                    }                }            }        }        while(!que.empty()){            ll u = que.top();            que.pop();            t += u;            ans += t;        }         printf("%lld\n", ans);    }    return 0;}