题解 P4409 【[ZJOI2006]皇帝的烦恼】

· · 题解

答案公式的严谨证明

本文并非原创,是总结了@木木! 和@Little_Ming 的想法而得出的.

设答案为A,则柿子是A=max\{a_1+a_2,a_2+a_3,...,a_n+a_1,\lceil\frac{\sum a_i}{\lfloor\frac n2\rfloor}\rceil\}

为什么呢?先证明必要性.

由于相邻两个将军勋章不能相同,因此A不小于任意两个将军勋章之和.由于每种勋章最多被分给\lfloor \frac n2\rfloor个将军,因此A不小于总勋章数除以\lfloor \frac n2\rfloor.

再证充分性.分奇偶两类讨论.

n为偶数时,显然有A不小于任意两个将军勋章之和是有合法方案的充分条件.不妨设a_i+a_{i+1}(a_n+a_1同理)是最大的相邻将军之和,则有

\frac n2(a_i+a_{i+1})\ge\sum a_i$,那么$A\ge a_i+a_{i+1}\ge\lceil\frac{\sum a_i}{\lfloor\frac n2\rfloor}\rceil

n为奇数时,设奇数位的余量r_{2k-1}为第2k-1的将军所选勋章集合的补集与第1个将军所选勋章集合的交集大小.(这也是@木木 的题解出问题的地方,由于定义出错,他的证明看起来十分不严谨并且可能是伪证)

显然有结果满足条件等价于r_n=a_1

情况一 ,当a_{2k}\le r_{2k-1}时,第2k的将军所选勋章集合为第一个将军所选集合的子集,由A\ge a_{2k}+a_{2k+1}可知r_{2k+1}=min(A-a_{2k+1},a_1),此后a_{2k+1}+a_{2k+2}\le A,a_{2k+2}\le A-a_{2k+1}\le r_{2k+1}继续满足条件,归纳可知r_n=min(A-a_n,a_1)=a_1

情况二 ,当a_{2k}>r_{2k-1}时,第2k的将军所选集合有a_{2k}-r_{2k-1}个不属于第一个将军所选集合,那么r_{2k+1}=min(r_{2k-1}+A-a_{2k}-a_{2k+1},a_1),由情况一后面的归纳可知,r_{2k+1}属于情况二,则r_{2k-1}不可能属于情况一,那么

r_{2k+1}=min(min(r_{2k-3}+A-a_{2k-2}-a_{2k-1},a_1)+A-a_{2k}-a_{2k+1},a_1) =min(r_{2k-3}+2A-a_{2k-2}-a_{2k-1}-a_{2k}-a_{2k+1},a_1+A-a_{2k}-a_{2k+1},a_1)

由于A-a_{2k}-a_{2k+1}\ge 0,

r_{2k+1}=min(r_{2k-3}+2A-a_{2k-2}-a_{2k-1}-a_{2k}-a_{2k+1},a_1)

归纳可知,当r_n由情况二产生时

r_n=min(r_1+\sum_{k=1}^{\lfloor \frac n2\rfloor}A-a_{2k}-a_{2k+1},a_1)

此时要使方案合法,则r_n=a_1

r_n=a_1\Leftrightarrow a_1=min(\sum_{k=1}^{\lfloor \frac n2\rfloor}A-a_{2k}-a_{2k+1},a_1) r_n=a_1\Leftrightarrow a_1\le\sum_{k=1}^{\lfloor \frac n2\rfloor}A-a_{2k}-a_{2k+1} r_n=a_1\Leftrightarrow \sum a_i\le\sum_{k=1}^{\lfloor \frac n2\rfloor}A

由于A是整数,

r_n=a_1\Leftrightarrow A\ge\lceil\frac{\sum a_i}{\lfloor\frac n2\rfloor}\rceil

(在@木木! 的题解中用的是不等式相加,并不能取等价于,因此他证明的"充分性"实际上也是必要性,是个伪证.)

至此,证明了A\ge max\{a_1+a_2,a_2+a_3,...,a_n+a_1,\lceil\frac{\sum a_i}{\lfloor\frac n2\rfloor}\rceil\}是方案合法的充要条件.由于答案最小,那么直接取到最小值即可.