题解 CF140C 【New Year Snowmen】

Itst

2019-11-04 21:41:18

Solution

结论挺显然的,但是证起来不太好证。 这里补一个CF tutorial里面的证明。 首先声明:我们的贪心策略是每一次选择出现次数最多的三个位置将其$-1$。 先求出每种数的出现次数,设最后的答案为$k$。把出现次数$>k$的数的出现次数设为$k$,因为多于$k$的部分没用。此时所有数的出现次数之和$\geq 3k$,否则一定不会存在方案。 考虑用数学归纳法证明命题:对于一个出现次数序列$\{r_i\}$,如果满足$\forall i , r_i \leq k$且$\sum r_i \geq 3k$,则若每一次选择三个出现次数最多的数$-1$,一定可以操作$\geq k$次。 证明: 当$k=1$时命题显然成立; 当$k>1$时,根据鸽巢原理,必定存在至少三个数不为$0$,所以一定可以进行操作。 如果序列中存在至少$3$个数$=k$,那么我们只需要每一次操作这三个数即可达成要求,不难得知这一定不会比每一次选择三个最大的数的方案优,所以一定存在方案。 否则如果只存在$\leq 2$个数$=k$,操作三个最大的数,则可以变为新的出现次数序列$\{r'_i\}$满足$\forall i , r'_i \leq k-1$且$\sum r'_i \geq 3(k-1)$。根据归纳这样的出现次数序列的操作次数不少于$k-1$,所以当前序列选择三个最大的数操作的操作次数不少于$k$。 这样我们就证明了贪心策略的正确性。代码诸位都放了,我就不放了= =