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

· · 题解

upd: 重写了，将代码换成正确的版本（之前手抽复制错了），并且让证明更加清晰（清晰了十七八倍）

我是来给那位 \Theta(n) 的大佬补个证明的。

另设答案为 A，以下将证明答案为：

A=\max(a_i+a_{i-1},\lceil\frac{\sum a_i}{\lfloor\frac{n}{2}\rfloor}\rceil)

这里认为 a_0=a_n。

充分性很好证明，A\geq \max(a_i+a_{i-1}) 显然，由于一个勋章最多分给 \lfloor\frac{n}{2}\rfloor 位将领，于是 A\geq\lceil\frac{\sum a_i}{\lfloor\frac{n}{2}\rfloor}\rceil。

接下来证明必要性。

首先，对于 2|n（n 为偶数）的情况 A=\max(a_i+a_{i-1})。利用归纳法可以简单证得。或者使用直觉式的证明方法，如果将可用的勋章想象成一个 [1,A] 的连续段，每个可用勋章用一个整数代表，那么偶数项从 A 开始往下取，而奇数项从 1 开始往上取，那么答案必定是最能顶的一对。

对于其他情况，假设 A>\max(a_i+a_{i+1})。由于 n 是奇数，如果 a_1 从 1 开始往上取得，方针则是偶数尽量往下取，奇数尽量往上取。

令奇数位的“余量”为它的最低一项距离 1 的距离（即如果用一个整数代表一个勋章，那么就是最小的整数减一），第 i 位的余量为 r_i。那么，可以轻易证得答案合法的充要条件是 r_n\geq a_1。自然 n=1 要特判。

为论述方便，令 2k-1 位的余量是 r，2k+1 位的余量是 r'，思路就是推出 r' 和 r 的关系。

如果 r\geq a_{2k}，则将所有 a_{2k} 安排到余量中，a_{2k+1} 则可以全部安排到上面，r'=A-a_{2k+1}。注意到 A>a_{2k}+a_{2k+1}，因此这么做不会导致重叠。

否则，将 r 个勋章安排到下面，a_{2k}-r 个勋章安排在最上方。a_{2k+1} 就在 a_{2k}-r 个勋章之下再继续取，最终 r'=r+A-a_{2k}-a_{2k+1}。同样注意到 A>a_{2k}+a_{2k+1}，因此这么做是合法的。

两种情况可以综合成一个统一的式子。我们可以注意到 r'\leq r+A-a_{2k}-a_{2k+1}。

柿子在第 n 位的时候也适用，并且根据定义，有 r_1=0。因此可以得到这么一个式子：

r_n\leq\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} A-a_{2k}-a_{2k_1}

答案成立的条件即为：

\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} A-a_{2k}-a_{2k_1}\geq r_n\geq a_1

即：

\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} A-a_{2k}-a_{2k_1}\geq a_1

将 A 提出来，并且简化剩下项的下标，可以得到：

\lfloor\frac{n}{2}\rfloor A-\sum_{k=2}^{n} a_k\geq a_1

再移项，将 \lfloor\frac{n}{2}\rfloor 移过去，就可以得到激动人心的式子：

A\geq \frac{\sum a_i}{\lfloor\frac{n}{2}\rfloor}

满足这个条件并同时 \geq\max(a_i+a_{i+1}) 的 A 就可以作为答案。

因此 A=\max(a_i+a_{i-1},\lceil\frac{\sum a_i}{\lfloor\frac{n}{2}\rfloor}\rceil)

附 AC 代码：

#include <cstdio>
using namespace std;

void chkmax(int& a,int b)
{
    if(a<b)
    {
        a = b;
    }
}

int ai[20005];

int main()
{
    int n,sum=0;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",ai+i);
        sum += ai[i];
    }

    int ans = 0;
    for(int i=1; i<n; ++i)
    {
        chkmax(ans,ai[i]+ai[i+1]);
    }
    chkmax(ans, ai[1]+ai[n]);
    chkmax(ans, (sum+(n>>1)-1)/(n>>1));

    printf("%d",ans);
}