uva 11729

题目大意：有n的部下，你可以花费bi时间为第i个人分配任务，第i个人可以通过时间j完成任务，每个人可以同时进行任务，但是不可以同时分配任务，最小化最后完成所有任务的时间

 

分析：可以同时进行任务，如果所有任务都能再安排后然后再下一个任务安排前结束，也就是s[i].b+s[i].j<s[i].b+s[i+1].b,如果是这样我们把完成所需要的时间最小的j放在最后一定是最优，所有我们将j从大到小排序，然后依次交代任务即可。(一般性证明可参考蓝书)

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
struct node{
    int b,j;
    node(){}
    node(int b,int j):b(b),j(j){}
    bool operator<(const node &rhs)const{
        return j>rhs.j;
    }
}s[maxn];
int n;
int main(){
    int kase=0;
    while(cin>>n&&n){
        for(int i=1;i<=n;i++)cin>>s[i].b>>s[i].j;
        sort(s+1,s+n+1);
        int ans=0,sum=0;
        for(int i=1;i<=n;i++){
            sum+=s[i].b;
            ans=max(ans,sum+s[i].j);
        }
        cout<<"Case "<<++kase<<": "<<ans<<endl;
    }
    return 0;
}