问题
https://vjudge.net/problem/UVA-1335
分析
如果n为偶数，那么就只需要求出相邻两个人的最大的和，就是所有礼物的总数
如果n为奇数，不能再使用上面的贪心的方法，使用二分的方法，编号为偶数的人尽量向前取，编号向后的人尽量向后取，left[i]代表每个人在[1,r_1]中取了几个，right[i]代表在[r_1+1,n]中取了几个，因为这里不需要输出解决方案，只需要记录每个人取了多少东西。
这里的r_1主要是起到了一个分界线的作用，偶数号从小到大取，奇数号从大到小取(为了满足相邻不重复)。如果最后1和n满足不重复说明合理，也就是left[n]==0，说明n不会取1-r_i之间的礼物。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>using namespace std;
typedef long long LL;
const int maxn=100000+5,Inf=0x3f3f3f3f;
int n,r[maxn],Left[maxn],Right[maxn];bool check(int s) {int x=r[1],y=s-r[1];Left[1]=r[1],Right[1]=0;for(int i=2;i<=n;++i){if(i&1){//尽量拿右边的礼物Right[i]=min(r[i],y-Right[i-1]);//还有剩下的再取左边的Left[i]=r[i]-Right[i];}else{//尽量拿左边的Left[i]=min(r[i],x-Left[i-1]);Right[i]=r[i]-Left[i];}}return Left[n]==0;
}int main(void){while(scanf("%d",&n)==1 && n){for(int i=1;i<=n;++i) scanf("%d",&r[i]);if(n==1){printf("%d\n",r[1]);continue;}r[n+1]=r[1]; //是一个环int L=0,R=0;for(int i=1;i<=n;++i) L=max(L,r[i]+r[i+1]); //最大的相邻和if(n%2==1){for(int i=1;i<=n;++i) R=max(R,r[i]*3);while(L<R){int mid=(L+R)/2;if(check(mid)) R=mid;else L=mid+1;}}printf("%d\n",L);}return 0;
}