分析：
提示都说是二分了
肯定就是二分一个种类数
现在问题是，我们怎么判断该种方案是否可行呢
我们选择dp
为什么是dp呢
因为dp比较diao
先看比较简单的，如果n是偶数，那么我们就可以把所有将士分成两部分
同一部分可以拥有颜色一样的徽章，那么答案就是相邻两个的加和最大值
那要是n为奇数呢，我们就不能这么simple了
这个时候第n个分到哪一部分无法立刻确定
那么关键问题就出现在第1个和第n个的冲突上
所以我们考虑用dp来递推最小和最大的冲突数量
maxn[i]表示在不与i-1发生冲突的前提下，与1号的最大冲突
minn[i]表示在不与i-1发生冲突的前提下，与1号的最小冲突
等一下，什么叫两者之间的冲突呢
其实每个人自己的勋章颜色各不同，不管他人，可能会重复的颜色
maxn[i]=min(a[i],a[1]-minn[i-1])
（minn[i-1]的颜色我们一定不能用，否则会和i-1冲突，a[1]剩下的颜色，最坏情况就是我用的都是这一部分的颜色）
因为要使i和1冲突尽可能大，而又不能与i-1冲突，
所以我们令i-1与1的冲突尽可能小，除去minn[i-1]，a[1]中的点都可以选，所以上面的式子得证。
minn[i]=max(0,a[i]-(x-a[i-1]-a[1]+maxn[i-1))
（尽量不冲突，也就是说x种颜色尽量少的分配给了i-1和1的冲突部分之后，剩下的如果不够a[i]，那么i和1一定会发生冲突）
我们希望冲突尽可能的小，那么也就是除了不得不冲突的情况，其他的都不冲突
那么如果计算不得不冲突的情况呢？
我们一共有x种颜色，x-a[i-1]-a[1]+maxn[i-1]表示x中除去与i-1冲突的，除去与1冲突的
（令i-1和1冲突最大，能保证剩下的点最多）所能选取的点，如果点数不足a[i]，那么必然要与1发生冲突。
最后判断是否可行，只需要判断minn[n]是否为0即可，因为推得时候保证与前一个不冲突。
注意二分答案的最小值不能是1，因为我们推的时候保证i不与i-1冲突，
所以最小值应该是相邻两个加和的最大值。
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=100001;
int n,limit=0,sum=0;
int a[N],minn[N],maxx[N];
int pd(int x)
{
minn[1]=maxx[1]=a[1];
for (int i=2;i<=n;i++)
{
maxx[i]=min(a[1]-minn[i-1],a[i]);
minn[i]=max(0,a[i]-(x-a[i-1]-a[1]+maxx[i-1]));
}
if (!minn[n]) return 1;
else return 0;
}
int main()
{
scanf("%d",&n);
a[0]=0;
for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i],limit=max(limit,a[i]+a[i-1]);
limit=max(limit,a[1]+a[n]);
int l=limit,r=sum;
int mid,ans=0x33333333;
while (l<=r)
{
mid=(l+r)>>1;
if (pd(mid))
{
ans=min(ans,mid);
r=mid-1;
}
else l=mid+1;
}
printf("%d",ans);
return 0;
}