UVALive 3177 长城守卫

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1178

http://7xjob4.com1.z0.glb.clouddn.com/8e1ee1ef5ea10e46ebda75b88b058f47

题意：n个人围圈，每人有不同或相同数量礼物，相邻礼物不能一样，求最少总礼物数。

思路: n是偶数：为相邻两人礼物数和的最大值；n是奇数：二分法选礼物数量，看是否可行，设第一个人礼物为前几种，编号为偶数的人尽量在前面取，奇数的人尽量在后面取，最后查看最后一人的礼物是否和第一个人的冲突。

#include <bits/stdc++.h>
using namespace std;

int n;
int r[100005],Left[100005],Right[100005];

int check(int p)
{
    int i,j;
    int x=r[1],y=p-r[1];
    Left[1]=x,Right[1]=0;
    for(i=2;i<=n;i++)
    {
        if(i%2==0)
        {
            Left[i]=min(x-Left[i-1],r[i]);
            Right[i]=r[i]-Left[i];
        }
        else
        {
            Right[i]=min(y-Right[i-1],r[i]);
            Left[i]=r[i]-Right[i];
        }
    }
    if(Left[n]==0)
        return 1;
    return 0;
}

int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF && n!=0)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&r[i]);
        }
        if(n==1)
        {
            printf("%d
",r[1]);
            continue;
        }

        int L=0,R=0;r[n+1]=r[1];
        for(i=1;i<=n;i++)   L=max(L,r[i]+r[i+1]);
        if(n%2==1)
        {
            for(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
",L);
    }
    return 0;
}