【牛客竞赛】Hamburger Steak 题解

题目描述

你有 $m$ 个锅和 $n$ 个汉堡，第 $i$ 个汉堡需要在锅里烹饪 $t_i$ 分钟。

对第 $i$ 个汉堡，你可以一次烹饪 $t_i$ 分钟，也可以分别烹饪 $a_i, b_i$ 分钟（$a_i + b_i = t_i$）。

你将从第0分钟开始烹饪，并尽可能快的完成烹饪，求具体的烹饪方法。

原题地址

注：一个汉堡同时只能在一个锅中烹饪，一个锅同时也只能烹饪一个汉堡，取出和放入汉堡的时间忽略不计，题目中涉及的时间均为正整数。

分析

最优的策略是，在结束前，尽量让所有的锅都在烹饪，比如三个汉堡，都要烹饪2分钟，有2个锅，那么最优策略显然是先放进去两个，一个烹饪一分钟后拿出来，再把最后一个还没烹饪的放进去，一直在烹饪的那个熟了以后，在把刚在烹饪一半的放进去，所以一共需要3分钟，这就是在结束前，尽量让所有的锅都在烹饪。

因为一个汉堡可以分别在两个锅里烹饪，也就是说可以烹饪两次。进一步讲，就是把所有需要的烹饪时间尽量地平均到每个锅里，如果可以，令 $sum$ 为所有汉堡的烹饪时间之和，那么所需时间是 $\lceil sum/m \rceil$。

那么什么时候是无法平均分配的呢？就是有一个汉堡的烹饪时间太长了，而一个汉堡又不能同时放在两个锅里烹饪，所以总得等它烹饪完。

综上，所需最短时间就是：

$$t = \max\!\left(MaxTime,\ \left\lceil \frac{sum}{m} \right\rceil\right)$$

那么怎么构造呢？

就在规定时间内，往锅里放尽量多的汉堡（从所需烹饪时间最长到最少），如果超出了 $t$，那么就把这个汉堡的烹饪时间分成两部分，把多余的那部分，放入下一个锅里，因为我们是降序排序的，所以放入下一个锅内的汉堡的烹饪时间绝对不会到当前汉堡在这个锅的烹饪时间（即不会出现一个汉堡同时在两个锅里烹饪）。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
 
const int maxN = 1e5 + 7;
 
int n, m;
long long sum, maxTime;
 
struct Steak {
    int  id;
    long long t;
}a[maxN];
 
bool cmp(Steak a, Steak b) {
    return a.t > b.t;
}
 
struct Ans {
    int k;
    int id[3];
    long long l[3], r[3];
 
    void add(int _id, long long _l, long long _r) {
        ++k;
        id[k] = _id; l[k] = _l; r[k] = _r;
        if(k > 1) {
            swap(id[1], id[2]);
            swap(l[1], l[2]);
            swap(r[1], r[2]);
        }
    }
}ans[maxN];
 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i].t);
        a[i].id = i;
        sum += a[i].t;
        maxTime = max(maxTime, a[i].t);
    }
    sort(a + 1, a + 1 + n, cmp);
    maxTime = max(maxTime, ((sum + m - 1) / m));
    int now = 1, panId = 1;
    long long lst = maxTime;
    while(now <= n) {
        if(a[now].t <= lst) {
            ans[a[now].id].add(panId, maxTime - lst, maxTime - lst + a[now].t);
            lst -= a[now].t;
            now++; 
            if(lst == 0) {
                lst = maxTime;
                ++panId;
            }
        }
        else {
            ans[a[now].id].add(panId, maxTime - lst, maxTime);
            a[now].t -= lst;
            panId++;
            lst = maxTime;
        }
    }
    for(int i = 1; i <= n; ++i) {
        printf("%d ", ans[i].k);
        for(int j = 1; j <= ans[i].k; ++j)
            printf("%d %lld %lld ", ans[i].id[j], ans[i].l[j], ans[i].r[j]);
        printf("\n");
    }
    return 0;
}