题目描述

https://www.acwing.com/problem/content/description/1397/

算法

(贪心)

题意分析：有两台机器共同工作，A机器可加工之后的物品再给B机器加工，求得A机器完成全部物品时的最短时间以及两台机器完成所有物品的最短时间

贪心思路：
问题①
从题目可以知道每台机器的完成效率是不同的，也就是工作时间有长短之分，那么我们可以让完成时间短的机器先工作，那么此时A机器的完成时间可以理解为某台机器的工作时间加上上一台机器的完成时间，这么说可以难以理解。举个栗子，比如洗衣服，三台洗衣机的完成时间分别是1，2，5，那么我们可以选择先让第一台机器工作，那么此时它完成的时间为1，虽然机器可以并行工作，但我们发现如果三台机器同时洗三件衣服，那么时间将是8，而如果让第一台洗完3件，则时间为3。
问题②
通过上述分析，B机器也可以采用同样的策略，但我们知道采用这种策略，它的时间是逐渐递增的，那么对于两种机器，最后的时间一定会很大，那么此时我们考虑，如果让B机器在A机器选择完成时间较快的机器时选择完成时间较短的机器，那么时间会比之前减少。这里可以理解一种互补的关系。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010;
int a[N], b[N]; //a表示A类第i个物品加工完成所需要的时间，b表示B类第i个物品加工完成所需要的时间
int n, m1, m2;

struct Node{
    int finish_time, cost;
    bool operator< (const Node &t) const{
        return finish_time > t.finish_time; //小根堆
    }
};

void work(int m, int f[])
{
    priority_queue<Node> q;

    for(int i = 1; i <= m; i ++)
    {
        int cost;
        cin >> cost;
        q.push({cost, cost});
    }

    for(int i = 1; i <= n; i ++)
    {
        auto t = q.top();
        q.pop();
        f[i] = t.finish_time;
        t.finish_time += t.cost;
        q.push(t);
    }
}

int main()
{
    cin >> n >> m1 >> m2;

    work(m1, a);
    work(m2, b);

    int res = 0;
    for(int i = 1, j = n; i <= n; i ++, j --)
        res = max(res, a[i] + b[j]); //取决于最慢完成的时间
    cout << a[n] << ' ' << res << endl;
    return 0;
}