当前位置:编程学习 > C/C++ >>

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;  
}  

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,