[Zjoi2006]trouble 皇帝的烦恼

Time Limit:1000MS  Memory Limit:65536K
Total Submit:54 Accepted:20

Description

经过多年的杀戮，秦皇终于统一了中国。为了抵御外来的侵略，他准备在国土边境安置n名将军。
不幸的是这n名将军羽翼渐丰，开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过 为防兵变，他决定先授予这些将军一些勋章，为自己赢得战略时间。
将军们听说他们即将被授予勋章都很开心，他们纷纷上书表示感谢。第i个将军要求得到ai枚不同颜色的勋章。但是这些将军都很傲气，如果两个相邻的 将军拥有颜色相同的勋章他们就会认为皇帝不尊重他们，会立即造反（编号为i的将军和编号为i+1的将军相邻；因为他们驻扎的边境可以类似看成一个圆形，所 以编号1和编号n的将军也相邻）。
皇帝不得不满足每个将军的要求，但对他们的飞扬跋扈感到很气愤。于是皇帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少 种颜色的勋章？

Input

第一行有一个整数n(1<=n<=20000)。
接下来n行每行一个整数ai，表示第i个将军要求得到多少种勋章。(1<=ai<=100000)

输出一个整数，即最少需要多少种勋章。

Output

4
2
2
1
1

Sample Input

4

Sample Output

Source

Day2
靠。。这道破题让我WAN次。。真是悲剧。。看来太不细心了囧。。。
首先这个题目很显然如果扫描的话，由于是环形的，可以把奖章看成两种，
第一种属于第一个人的，第二种是不属于的。
那么如果Dp的话要记录种数，显然要TLE。。
所以要二分答案。。
然后可以发现每个人能拿的第一种奖章数是一个区间。。
假设第i个人的区间是l,r
那么列出一系列条件（这点一定要考虑周全，不然WA）。。
算出第i+1个人的区间，然后看看第N个人的区间是否包含0。。
Code：

#include <cstdio>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
const int maxn=20000,inf=~0U>>1;
using namespace std;
int a[maxn],n,l[maxn],r[maxn];
inline void checkmin(int&x,int c){if(x>c)x=c;}
inline void checkmax(int&x,int c){if(x<c)x=c;}
bool Check(int K)
{
l[0]=r[0]=a[0];
for(int i=1;i<n;i++)
{
l[i]=-inf;r[i]=inf;
if(a[i-1]+a[i]>K)return false;
checkmin(r[i],a[0]-l[i-1]);
checkmin(r[i],a[0]);
checkmin(r[i],a[i]);
checkmax(l[i],a[0]+a[i-1]+a[i]-K-r[i-1]);
checkmax(l[i],a[i]-K+a[0]);
checkmax(l[i],0);
if(l[i]>r[i])return false;
}
return l[n-1]<=0;
}
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);rep(i,n)scanf("%d",a+i);
int l=0,r=500000;
while(l+1<r)
{
int m=l+r>>1;
if(Check(m))r=m;else l=m;
}
printf("%dn",r);
}