2021牛客暑期多校训练营6 F、Hamburger Steak

题目大意

你有 $n(10^5)$ 个汉堡代煎，每个汉堡要被煎制 $t_i$ 分钟，你现在只有 $m$ 口锅，每个汉堡可以分两次煎制也可以一次煎完。问完成 $n$ 块汉堡全部的煎制最小的完成时间是多少？

Solution

考点：思维题

因为你只有 $m$ 口锅，并且所有汉堡需要煎制的时间也给你了，那么你就可以知道对于工作时间最长的一口锅而言，它需要工作的最长时间。

首先，我们最小的完成时间都应该是 $\max(t_i)$ ，也就是对于锅而言最小的最长时间。

但是我们可以感觉到这个最长时间不一定就是锅的工作时间，例如 $m=3,t=\{6,6,6,2\}$ ，那么就一定有 $m*\max(t_i)\ge\sum t_i$ 但是很显然这个式子是错误的，所以我们选择的最长工作时间是 $\max(t_i)$ 不一定是正确的，但是我们可以解出当前模式下的最大值应该是 $\displaystyle \lceil \frac{\sum t_i}{m} \rceil$ 。

那么我们知道了每口锅需要工作的最大时间，那么我们就让每口锅工作满换再换下一口就行了，因为我们已经保证一口锅的时间要大于等于任何的一个 $t_i$ ，所以 $2$ 口锅一定可以完成任意一个汉堡的煎制工作。

typedef tuple<int, int, int> tup;
const int N = 1e5 + 7;
struct Node {
    vector<tup> a;
}ans[N];
ll n, m;
int p[N];

int solve() {
    n = read(), m = read();
    ll sum = 0;
    for (int i = 1; i <= n; ++i)    sum += p[i] = read();
    ll maxi = *max_element(p + 1, p + 1 + n);
    maxi = max(maxi, (sum + m - 1) / m);

    int pos = 1, now = 0;

    for (int i = 1; i <= n; ++i) {
        if (now + p[i] <= maxi) {
            ans[i].a.push_back({ pos,now,now + p[i] });
            now += p[i];
        }
        else {
            ans[i].a.push_back({ pos + 1,0,p[i] - (maxi - now) });
            ans[i].a.push_back({ pos,now,maxi });
            ++pos;
            now = p[i] - (maxi - now);
        }
        if(now == maxi)    ++pos,now = 0;
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i].a.size() << " ";
        for (auto& [id, l, r] : ans[i].a)
            cout << id << " " << l << " " << r << " ";
        cout << endl;
    }

    return 1;
}