思路
贪心加模拟。由于要让所有客人满意,因此每个 $d_i$ 时段贝茜都必须用来迎接客人。除此之外的其它时段,贝茜有两种选择,要么休息,要么准备菜品。贪心,如果时段 $t_i$ 存在已经接收到但还未准备好的订单,贝茜就去准备它。如果存在多个这样的订单,优先准备客人最早到达的那个。如果没有订单需要准备,贝茜就休息。
总结:
- 客人到达的时段迎接客人。
- 没有订单需要准备就休息。
- 有订单需要准备,选择客人最早到达的那个。
证明:只要问题有解,则贪心一定是一个可行解。
-
由于以上三个条件都是确定的,因此贪心解中每个时段的任务是确定的。
-
若问题有解,对于任意一个可行解,通过调整都可以转换为贪心解,且不影响它的可行性。具体过程为:按 $1 \sim n$ 的时段顺序依次比较可行解和贪心解,当找到第一次不同时,贪心解一定是在准备订单,且可行解不可能在迎接客人:
- 若可行解选择休息,如下图情况一所示,贪心解在 $t_1$ 时段准备第 $i$ 个订单,可行解必须在 $d_i$ 之前的某个时段 $t_2$ 准备好第 $i$ 个订单。此时,在可行解中交换 $t_1, t_2$ 时段的任务,仍然能在客人到达之前准备好订单 $i$,且对其它订单没有影响,仍是可行解,且在 $t_1$ 时刻与贪心解的选择相同。
- 若可行解也在准备订单,如下图情况二所示,贪心解在 $t_1$ 时段准备第 $i$ 个订单,可行解在 $t_1$ 时段准备第 $j$ 个订单。由于贪心解准备的一定是客人最早到达的订单,因此 $d_i < d_j$,可行解必须在 $d_i$ 之前的某个时段 $t_2$ 准备好第 $i$ 个订单。此时,在可行解中交换 $t_1, t_2$ 时段的任务,仍然能在客人到达之前准备好第 $i$ 和第 $j$ 这两个订单,且对其它订单没有影响,仍是可行解,且在 $t_1$ 时刻与贪心解的选择相同。
重复以上过程,一定能将可行解转为贪心解,且可行性不变。
情况一:
准备第 i 个订单
贪心解:--------|-----------------------|------------
可行解:--------|--------------|--------|------------
t1 t2 di
休息 准备第 i 个订单
-----------------------------------------------------
情况二:
准备第 i 个订单
贪心解:--------|-----------------------|--------|---
可行解:--------|--------------|--------|--------|---
t1 t2 di dj
准备第 j 个订单 准备第 i 个订单
时间复杂度 $O(nm)$,空间复杂度 $O(n)$。
#include <iostream>
#define loop(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
const int N = 110;
int n, m;
struct Order { int s, d, c; } ord[N];
int ans[N];
bool work() {
loop(t, 1, n) {
auto& job = ans[t];
loop(i, 1, m) {
auto& [s, d, c] = ord[i];
if (d == t) {
if (c) return false;
job = m + 1;
break;
}
if (s <= t && c
&& (!job || ord[job].d > d))
job = i;
}
// ord[0], ord[m + 1] 不存在,
// 改变它们没有影响
ord[job].c--;
}
return true;
}
int main() {
scanf("%d%d", &n, &m);
loop(i, 1, m) {
auto& [s, d, c] = ord[i];
scanf("%d%d%d", &s, &d, &c);
}
if (work()) loop(i, 1, n) printf("%d ", ans[i]);
else puts("-1");
return 0;
}