UVA11729 Commando War【贪心】

问题链接：UVA11729 Commando War。

问题简述：有n个部下需要完成一项任务，给第i个部下交代任务需要Bi时间，执行任务需要Ji时间，要求尽早完成任务，请输出最后完成任务需要的最小总时间。

这个问题是一个典型的贪心法问题，求完成任务的最短时间。用C++编程比较方便。

程序说明：

程序中，比起用结构表示，每一项任务用一个类对象表示，程序处理起来比较方便，所以实现了一个简单的类job。

排序时，任务J按时间从大到小执行，可以得到最短的完成任务时间。但是，如果任务的时间相同，应该让交代任务时间较短的任务优先执行。

AC通过的C++语言程序如下：

/* UVA11729 Commando War */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 10000;

class job {
public:
    int b, j;

    job(int b, int j):b(b), j(j){}

    bool operator < (const job& r) const {
        return (j == r.j) ? b < r.b : j > r.j;
    }
};

vector<job> myjob;

int main()
{
    int n, b, j, caseno=0;

    while(scanf("%d", &n) != EOF && n != 0) {
        myjob.clear();

        for(int i=0; i<n; i++) {
            scanf("%d%d", &b, &j);
            myjob.push_back(job(b, j));
        }

        sort(myjob.begin(), myjob.end());

        int sum = 0, ans = 0;
        for(int i=0; i<n; i++) {
            sum += myjob[i].b;
            ans = max(ans, sum + myjob[i].j);
        }

        printf("Case %d: %d\n", ++caseno, ans);
    }

    return 0;
}