UVA11729 Commando War

思路

简单贪心

按需要时间，需要多的先安排，需要时间一样多的先安排交代需要时间少的

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
struct task{
    int a,b;
}Q[1100];
bool cmp(task a,task b){
    // return a.a==b.a?a.b>b.b:a.a<b.a;
    return a.b==b.b?a.a<b.a:a.b>b.b;
}
int main(){
    int cnt=0;
    while(scanf("%d",&n)&&n!=0){
        cnt++;
        for(int i=1;i<=n;i++)
            scanf("%d %d",&Q[i].a,&Q[i].b);
        sort(Q+1,Q+n+1,cmp);
        int rest=0,tot=0;
        for(int i=1;i<=n;i++){
            rest=max(rest-Q[i].a,0);
            tot+=Q[i].a;
            rest=max(rest,Q[i].b);
        }
        tot+=rest;
        printf("Case %d: %d
",cnt,tot);
    }
    return 0;
}