【题解】UVa P11729 【Commando War】

很显然,执行较长的任务应该先交代,于是就可以的到一个贪心算法:按照$J$从大到小排序,然后依次交代就好

#include<cstdio>
#include<vector>
#include<algorithm>

namespace OI{
    using std::vector;
}
using namespace OI;

class Pair{
    public:int j,b;
    bool operator < (const Pair &x) const{
        return j > x.j;
    }
};

inline int max(int a,int b){
    return a > b ? a : b;
}

int main(){
    int n,b,j,Case = 1;
    while(scanf("%d",&n) == 1 && n){
        vector<Pair> v;
        for(int i = 0;i < n;i++){
            scanf("%d %d",&b,&j);
            v.push_back(Pair{j,b});
        }
        sort(v.begin(),v.end());
        int s = 0,ans = 0;
        for(int i = 0;i < n;i++){
            s += v[i].b;
            ans = max(ans,s + v[i].j);
        }
        printf("Case %d: %d\n",Case++,ans);
    }
    
    return 0;
}