UVa 11729 - Commando War

分析：有n个部下，每个部下需要完成一项任务，第i个部下需要你花bi分钟交代任务，ji分钟完成，问你完成所有任务的最短时间。（不能同时交代任务，但可以有多个部下正在完成任务）

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <string>
#include <numeric>
#include <algorithm>
#include <functional>
#include <iterator>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <complex>
#include <ctime>

typedef long long LL;
const double pi = acos(-1.0);
const long long mod = 1e9 + 7;
using namespace std;

struct Job
{
    int j,b;
    bool operator < (const Job &x) const
    {
        return j > x.j;
    }
};

int main()
{
    //freopen("int.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int N;
    int b,j;
    int kase = 1;
    while(scanf("%d",&N) && N)
    {
        vector <Job> v;
        for(int i = 0;i < N;i++)
        {
            scanf("%d %d",&b,&j);
            v.push_back((Job){j,b});
        }
        sort(v.begin(),v.end());
        int s = 0;
        int ans = 0;
        for(int i = 0;i < N;i++)
        {
            s += v[i].b;
            ans = max(ans,s + v[i].j);
        }
        printf("Case %d: %dn",kase++,ans);
    }
    return 0;
}