算法 UVA 11729

例2：假设当前小光有n个部下，每个部下需要完成一项任务。第i个部下需要小光花Bi分钟交代任务，然后他会立刻独立地、无间断地执行Ji分钟后完成任务。小光需要选择交代任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。注意，不能同时给两个部下交代任务，但部下们可以同时执行他们各自的任务。
Input

输入包含多组数据，每组数据的第一行为部下的个数n（1<=n<=1000)；以下n行，每行两个正整数B和J(1<=B<=10000,1<=J<=10000)，即交待任务的时间和执行任务的时间。输入结束标志为n=0。
Output

对组每组数据，输出所有任务完成的最短时间。具体输出格式见样例，用Case开头，Case以后输出当前数据的序号，然后输出答案。
Sample Input
3
2 5
3 2
2 1
3
3 3
4 4
5 5
0
Sample Output
Case 1: 8
Case 2: 15

//2019.4.20 突击战

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct Job

{

    int j, b;

    bool operator < (const Job& x) const {

        return j > x.j;

    }

};

int main()

{

    int n, b, j, kase = ;

    while (scanf_s("%d", &n) ==  && n)

    {

        vector<Job> v;

        for (int i = ; i < n; i++)

        {

            scanf_s("%d%d", &b, &j);

            v.push_back({j, b});

        }

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

        int s = , ans = ;

        for (int i = ; i < n; i++)

        {

            s += v[i].b;

            ans = max(ans, s + v[i].j);

        }

        cout << "Case " << kase++ << ": " << ans << endl;

    }

    return ;

}

巴特西

算法 UVA 11729

最新文章

热门文章