题目意思是派遣一些军队去杀n条龙,杀死一条龙需要派遣ai个人,会死掉bi个人,问你最少派遣多少人可以杀死所有龙。


贪心题,比赛的时候没想出来排序的数,一直想的是按派遣人排还是按死的人排,后来freeloop说是按存活最多的排。然后,,,我想如果派我去打战估计损失惨重啊。。。



地址:http://codeforces.com/gym/101149/problem/B


代码:

StatusAccepted
Time93ms
Memory4408kB
Length748


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=200005;
typedef long long LL;
struct Node{
    int s, t, c;
    bool operator<(const Node &cmp) const{
        return c>cmp.c;
    }
}node[maxn];
int n;
LL ans;
int main()
{
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            scanf("%d%d", &node[i].s, &node[i].t);
            node[i].c=abs(node[i].s-node[i].t);
        }
        sort(node, node+n);
        ans=0;
        LL now=0;
        for(int i=0;i<n;i++){
            if(node[i].s>now){
                ans+=node[i].s-now;
                now=node[i].s;
            }
            now-=node[i].t;
        }
        printf("%lld\n", ans);
    }
    return 0;
}