题解 P4409 [ZJOI2006]皇帝的烦恼

· · 题解

解题思路：

首先想到的是（错误的）贪心。

对于任意两个相邻的将军（包括第一个和最后一个），至少需要两人勋章之和的勋章，于是直接取所有的最大值。

错误的原因也很简单——没有考虑第一个和最后一个是相邻的。

例如有三个人，需求都是1，这个贪心的结果是2，实际显然为3。

感觉贪心没什么大问题，能不能抢救一下呢？

顺着刚才的思路往下想，其实发现只有最后一个和第一个有冲突，为什么不能抢救一下呢？

可以发现，每一个勋章其实只能让 \dfrac{n}{2} 个将军获得，否则就会冲突。

还是看一开始的反例，发现问题其实是出在每一个勋章都给了2个人，其实不可能，在那种情况下每个勋章最多只能给1个人。

那么就可以总结出另一个式子，也就是\dfrac{\sum^{n}_{i=1}a_i}{\left\lfloor\dfrac{n}{2}\right\rfloor}， 分母意思是每个徽章最多能给予的将军数，分子表示将军所需的勋章总数，整个式子意思就是把每个勋章作用发挥到最大至少需要的勋章数

代码：

#include<cstdio>
using namespace std;
int max(int a,int b){if(a>b)return a;return b;}
int n,a[20005],ans,tot;
int main(){
    scanf("%d",&n);
    if(n==1)return 0&scanf("%d",&a[1])&printf("%d",a[1]);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ans=max(ans,a[i]+a[i-1]);
        tot+=a[i];
    }
    ans=max(ans,a[1]+a[n]);
    ans=max(ans,(tot+(n/2)-1)/(n/2));
    printf("%d",ans);
    return 0;
}