【题解】P3586 LOG

在浏览题解的过程中，我发现大部分题解对于此题的核心结论的证明都比较粗略。因此，在这篇题解中，我将详细证明这一结论： **在自然数序列 $\{a_n\}$ 上进行 $s$ 次操作：每次选择其中 $c$ 个非零数，将它们都减去 $1$。记序列中大于等于 $s$ 的数的个数为 $cnt$，小于 $s$ 的数的和为 $sum$。求证：** **$sum \geqslant s(c-cnt)$ 是该序列能进行s次操作的充分必要条件。** ------------ ### PART 1 充分性证明 非常显然。为了能够使操作次数尽量多，这 $cnt$ 个大于等于 $s$ 的数每次都会用上，则每次操作只需要在剩下的数中选出 $c-cnt$ 个，$s$ 次操作一共在剩下的数中减去了 $s(c-cnt)$ 的值。剩下的数的和 $sum$ 必然有 $sum \geqslant s(c-cnt)$。 ------------ ### PART 2 必要性证明 $sum \geqslant s(c-cnt)$ 时，是否一定能进行 $s$ 次操作？ 证明方法：数学归纳法。 不考虑那 $cnt$ 个大于等于 $s$ 的数，剩下 $m=n-cnt$ 个数构成另一序列 $\{b_m\}$，$s$ 次操作每次只需从中取出 $d=c-cnt$ 个非零数减去 $1$。我们要证明的结论就等价于： **已知序列 $\{b_m\}$ 的m个元素之和 $sum \geqslant s\times d$，且对于任意元素都有 $b_i<s$。每次操作从中取出 $d$ 个非零数减去 $1$。求证：能够进行至少 $s$ 次这样的操作。即：$s$ 次的每次操作前，序列中都有至少 $d$ 个元素大于 $0$。** 第一步首先证明：**第一次操作之前序列中有至少 $d$ 个元素大于 $0$。** 使用反证法：假如序列中只有 $d'<d$ 个非零数。这 $d'$ 个数都小于 $s$，其它数都为 $0$，则序列中所有数的和 $sum'<d'\times s<d\times s \leqslant sum$，出现矛盾。得证。 接下来开始**递推归纳**: 第一次操作之后，我们还需进行 $s'=s-1$ 次操作，而本次操作后得到的新序列的元素之和 $sum'=sum-d\geqslant (s-1)\times d$，即有 $sum' \geqslant s'\times d$。我们把下一次操作看成对于这个新序列的第一次操作，我们就回到了第一步。 但我们还不能直接用第一步证明的结论，因为两个问题的条件不完全相同：新序列上并不能保证**对于任意元素都有 $b_i<s'$**。如何解决？ 注意到：操作后新序列中不满足 $b_i<s'=s-1$ 的元素，一定是操作前序列中大小为 $s-1$ ，且本次操作没有被选中减去 $1$ 的元素。 对于每一次操作，我们的选取策略是：每次在操作前序列中选出**最大**的 $d$ 个数减去 $1$。记在操作前序列中大小为 $s-1$ 的元素个数为 $x$。这种策略之下，若 $x\leqslant d$，则这 $x$ 个数都能被选中并减去 $1$; 若 $x>d$，我们会剩下 $y=x-d$ 个元素不满足 $b_i<s'$。不过这 $y$ 个元素都恰好等于 $s'$，我们可以把它们看做在最初的问题上那些大于等于 $s'$ 的、每次操作都会用到的元素，并再次将它们从序列中除去，得到新的序列 $\{p_{m-y}\}$。序列 $\{p_{m-y}\}$ 满足所有元素都小于 $s'$。 于是，在以后的每一次操作中，我们每次只用再选取 $d'=d-y$ 个元素，除去那 $y$ 个元素后，序列 $p$ 的元素之和 $sump$ 有：$sump=sum'-y\times s' \geqslant s'\times d-y\times s' =s'\times (d-y)$； 而 $s'\times d'=s'\times (d-y)$，满足 $sump\geqslant s'\times d'$。 到此，我们的问题转化成了： **已知序列 $\{p_{m-y}\}$ 的 $m-y$ 个元素之和 $sump \geqslant s'\times d'$，且对于任意元素都有 $p_i<s'$。 每次操作从中取出 $d'$ 个非零数减去 $1$。证明：在该序列上能进行 $s'$ 次操作。** 这时我们便可以借助第一步的证明，再进行一次操作，使 $s'$ 变成 $s'-1$ 。用类似的方式转化问题，$s'$ 不断减小，直到为 $0$，我们的归纳证明就完成了。 ------------ ### 后记 关于此题，大家还可以看看[P5815扑克牌](https://www.luogu.com.cn/problem/P5815)，它实质上是本题中每次询问时 $c=n-1$ 的特殊情况。不过那一题问的是 最多进行多少次操作 ，而对于这类问题，我们更擅长对答案的判定，因而有了二分答案的做法。 本题解侧重于数学证明。然而在实际做题时，我们难以猜出结论并完全证明，因而本题解仅作学术参考为宜。 蒟蒻的第一篇题解，难免有疏漏之处，祈请各位读者不吝指正。