自动搬运

查看原文

来自洛谷，原作者为

	周子衡 Shadow is the light!

搬运于2025-08-24 22:23:51，当前版本为作者最后更新于2020-08-20 17:15:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这篇题解将给出详细的证明。如果我能拿到自己考场代码应该会贴（不过看起来希望渺茫）。

看到题目感觉无从下手。观察数据范围，发现一个奇怪的限制 $n-2\leq m$，而且还专门给出了 $m=n-1$ 和 $m\geq n-1$ 的部分分，我们不妨从此入手思考。

对于 $m=n-1$，枚举 $n=2,3$ 发现都一定有解。我们不妨尝试直接将 $n$ 向 $n-1$ 转化：不失一般性，令 $d_1\leq d_2\leq \cdots\leq d_n$。我们发现应该要尽量先用光少的那些材料，而且少的尽量要配大的。可以证明下面两条引理：

引理一：$d_1 < k$。

证明： 用反证法。假设 $d_1\geq k$，那么 $d_2,...,d_n\geq k$，则 $d_1+\cdots+d_n\geq nk>(n-1)k=d_1+\cdots+d_n$。显然矛盾，故命题得证。

引理二：$d_1+d_n\geq k$。

证明： 用反证法。假设 $d_1+d_n\leq k-1$，那么 $d_n\leq k-1-d_1$，则 $d_1+d_2+\cdots+d_n\leq d_1+(n-1)(k-1-d_1)=(n-1)k-(n-1)-(n-2)d_1 < (n-1)k$，矛盾，所以 $d_1+d_n\geq k$。

综合上面两条引理，我们可以一次把 $d_1$ 用光，同时用 $d_n$ 填补空缺，显然是可行的。这样就成功将 $n$ 的情况转化成了 $n-1$ 的情况。而 $n=2$ 时直接放一起即可。综上，我们成功对于 $m=n-1$ 的任意情况构造出了一组解。

直接模拟的时间复杂度为 $O(n^2)$；可以简单用数据结构优化到 $O(n\log n)$，虽然本题中没有必要。

对于 $m\geq n$ 的情况，考虑向 $m=n-1$ 转化。同上令 $d_1\leq \cdots\leq d_n$，显然可证

引理三： $d_n\geq k$。

证明： 如果 $d_n < k$，则 $d_1+d_2+\cdots d_n < nk\leq mk=d_1+d_2+\cdots d_n$。矛盾。

所以我们用 $d_n$ 单独做一道菜，就可以令 $m$ 减少 $1$。这样就转化为 $m=n-1$ 的情况了。时间复杂度 $O(mn)$ 或 $O(m\log n)$。

接下来是最后的部分：$m=n-2$。

先手推一下 $n$ 较小的情况，发现 $n=3$ 必定无解，$n=4$ 是有解当且仅当存在两个 $d$ 加起来等于 $k$。也就是说，我们似乎要将这个问题向 $m=n-1$ 转化；把 $n$ 个物品分为两个集合，如果两个集合都能找到 $m=n-1$ 的方法，那么加起来就有一个 $m=n-2$ 的方法了。也就是说

引理四： 问题有解当且仅当能找到一个集合 $U=\{1,...,n\}$ 的子集 $S$，使得：

• 记 $x=|S|$ 为 $S$ 的大小，则 $\sum_{i\in S}d_i=(x-1)k$。

证明：

• 充分性： 显然对于集合 $S$ 和 $T=U-S$，都是一个满足 $m=n-1$ 的子问题，而我们已经证明过了 $m=n-1$ 必定有解，则对 $S,T$ 分别构造解即可。

• 必要性： 考虑构造一张图 $G$，$G$ 中有 $1,...,n$ 这些节点，如果两种原料在一道菜里同时选用则连一条边。发觉 $G$ 中至多有 $n-2$ 条边，则 $G$ 一定不连通。设 $G$ 有一个连通块 $S$，则相当于 $S$ 必须满足 $m=n-1$ 的有解约束，即 $\sum_{i\in S}d_i=(x-1)k$。证毕。

总之，只要我们能找到一些物品的集合 $S$ 满足 $\sum d=(|S|-1)k$，就能构造出符合题意的解。如何求这个 $S$ 呢？显然考虑做背包 DP。而由于右边带了一个 $|S|$，我们再做一步转化，将 $|S|k$ 移到左边，即要求

$\sum (d-k)=-k$

这样就变成一道经典的 01 背包问题了。直接求解的时间复杂度为 $O(n\sum d_i)=O(n^2k)$，用 bitset 优化即可做到 $O(\dfrac{n^2k}{w})$。

其他想说的话：

• 这题确实是一道锻炼思维的题，据我个人观察，考场上坐我旁边的选手们人均思考了一小时以上。
• 我大致想出了正解的思路，但没有想出 bitset 优化，前边 $n\leq 4$ 的特判又挂了（哈哈哈哈哈），感觉 $100->85$ 没什么，$85->70$ 确实是自己的水平问题……
• 希望以后 NOI 能多出今年这样的思维好题吧。