[ZJOI2006]皇帝的烦恼

Posted on | In

今天打摆被抓有点烦

正解是二分+$DP$，但是先想想怎么贪心乱搞

可能相邻两个将军所需徽章数之和的最大值就是答案？？

不难发现，当$n$为奇数时显然不成立

考虑每一种徽章最多可以给$\lfloor \frac {n} {2} \rfloor$个人

所以$ans$最大不会超过$\lceil \frac{\sum a[i]}{\lfloor \frac {n} {2} \rfloor} \rceil$

最后把上面的两种情况取最大值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int ans,sum,a[100001];
inline int read () {
    char ch=getchar(); int num=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
    return num;
}
int main () {
    register int n=read();
    for(register int i=1;i<=n;++i)
		a[i]=read(),sum+=a[i];
    ans=a[1]+a[n];
    for(register int i=1;i<n;++i)
		ans=max(ans,a[i]+a[i+1]);
	ans=max(ans,(sum+(n>>1)-1)/(n>>1));
    printf("%d\n",ans);
    return 0;
}