UVA 11729 Commando War

根據任務時間從大到小排序，保存當前士兵以後能夠和其他人共同進行的時間。求出差的最大值，加上交代每個士兵任務這個必須時間就是答案。

 
#include<cstdio>  
#include<algorithm>  
#include<iostream>  
#include<cstring>  
using namespace std;  
struct node{int x,y;}man[1005];  
int last[1005];  
bool cmp(const node &a,const node &b)  
{  
    return a.y>b.y;  
}  
int main()  
{  
    int n;  
    int cas=1;  
    while(scanf("%d",&n)&&n)  
    {  
        int ans=0;  
        int sum=0;  
        last[n]=0;  
        for(int i=1;i<=n;i++)  
        {  
            scanf("%d%d",&man[i].x,&man[i].y);  
            sum+=man[i].x;  
        }  
        sort(man+1,man+1+n,cmp);  
        for(int i=n-1;i>=1;i--)  
        {  
            last[i]=last[i+1]+man[i+1].x;  
        }  
        for(int i=1;i<=n;i++)  
        {  
            if(man[i].y>last[i]) ans=max(ans,man[i].y-last[i]);  
        }  
        printf("Case %d: %d\n",cas++,ans+sum);  
    }  
    return 0;  
}