本文主要是介绍ZJOI2006皇帝的烦恼，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
时间限制: 1000ms
空间限制: 262144kB
题目描述
经过多年的杀戮，秦皇终于统一了中国。为了抵御外来的侵略，他准备在国
土边境安置n 名将军。
不幸的是这n 名将军羽翼渐丰，开始展露他们的狼子野心了。他们拒绝述职、
拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过为
防兵变，他决定先授予这些将军一些勋章，为自己赢得战略时间。
将军们听说他们即将被授予勋章都很开心，他们纷纷上书表示感谢。第i 个
将军要求得到a
i枚不同颜色的勋章。但是这些将军都很傲气，如果两个相邻的将
军拥有颜色相同的勋章他们就会认为皇帝不尊重他们，会立即造反（编号为i 的
将军和编号为i+1 的将军相邻；因为他们驻扎的边境可以类似看成一个圆形，所
以编号1 和编号n的将军也相邻）。
皇帝不得不满足每个将军的要求，但对他们的飞扬跋扈感到很气愤。于是皇
帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少
种颜色的勋章？
输入格式：
输入文件第一行有一个整数n(1<=n<=20000) 。
接下来n 行每行一个整数ai ，表示第i 个将军要求得到多少种勋章。
(1<=ai<=100000)
输出格式：
输出一个整数，即最少需要多少种勋章。
样例输入：
4
2
2
1
1样例输出：
4数据范围：
n<=20000
ai<=100000
时间限制：
1s
空间限制：
256M
主要思路：
首先，是二分，二分徽章的种类数。
check:
我们定义两个数组。
我们让奇数从n开始拿，偶数从1开始拿
f[i] = 1~i-1符合题目要求，i~i-1也符合要求，1和i最多重合几个徽章。
g[i] = 1~i-1符合题目要求，i~i-1也符合要求，1和i最少重合几个徽章。
接下来是转移：
我们知道，如果g[i-1]越小，则f[i] 越大。
那么f[i] = max(a[i],a[1]-g[i-1]);
相同的
g[i] = min(0,a[1]-(mid-a[1]-a[i-1])-f[i-1]);
然后return g[n] == 0;
最后就是这样的代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[100010];
int f[100010],g[100010];
bool check(int mid)
{f[1] = g[1] = a[1];for(int i=2;i<=n;i++){f[i] = min(a[i],a[1]-g[i-1]);g[i] = max(0LL,a[i]-(mid-a[1]-a[i-1])-f[i-1]);}return g[n] == 0;}
signed main()
{
// freopen("sample (12).in","r",stdin);ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int ans=0;for(int i=1;i<=n;i++){ans = max(a[i]+a[i+1],ans);}ans = max(ans,a[n]+a[1]);if(n%2 == 0){cout<<ans;return 0;}int l=ans,r=300000;int ans1=0;
// cout<<check(150000);while(l<=r){int mid = (l+r)/2;
// cout<<l<<' '<<r<<' '<<mid<<'\n';if(check(mid)){ans1 = mid;r = mid-1;}else{l = mid+1;}}cout<<ans1;return 0;
}这篇关于ZJOI2006皇帝的烦恼的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
