Uva 11729 Commando War 贪心这么像思维怎么办 U•ェ•*U

原题链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=2829

题意：首长给士兵交代任务，交代任务需要时间b，士兵执行任务需要时间j，首长必须一个个交代任务，不能同时给两个人交代，交代任务的同时士兵可以执行任务。问花费的最少时间。

思路：

根据题意，很容易想到通过调整给士兵交代任务顺序来调整所用时间 ，那么在调整顺序的时候，如图，X和Y交换位置，要想交换后(Y在前X在后)的用时没有交换前(X在前Y在后)的优，满足B[X]+B[Y]+J[Y]

Hint：

    s+=dr[i].b;//当前任务的开始执行时间
    ans=max(ans,s+dr[i].j)//更新任务执行完毕时的最晚时间

完整代码：

#include 
#include 
#include 
using namespace std;
#define N 10005

struct node{
    int b,j;
}dr[N];
bool cmp(node a,node b){
    return a.j>b.j;
}
int main(){
    int n,p=1;
    while(scanf("%d",&n)!=EOF&&n){
        for(int i=0;i){
            scanf("%d%d",&dr[i].b,&dr[i].j);
        }
        sort(dr,dr+n,cmp);
        int s=0,ans=0;
        for(int i=0;i){
            s+=dr[i].b;
            ans=max(ans,s+dr[i].j);
        }
        printf("Case %d: %d\n",p++,ans);
    }
    return 0;
}