LA 3177 长城守卫

n为偶数的时候比较简单，就是相邻两个守卫的礼物和的最大值。

首先这是个下限，其次这个值也满足题目要求，所以这就是答案了。

当n为奇数的时候上限是守卫索要礼物的最大值的三倍。

这也很容易理解，比如n=5，r_i都为1的时候，每个人拿到的礼物是1,2,1,2,3

有了上限有了下限就可以二分找出答案来了。

test函数的作用就是测试p种礼物能否满足要求。

//#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; 

const int maxn = 100000 + 10;
int n, r[maxn], left[maxn], right[maxn];

bool test(int p)
{
    int x = r[1], y = p - x;
    left[1] = x; right[1] = 0;
    for(int i = 2; i <= n; ++i)
    {
        if(i & 1 == 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)
{
    #ifdef LOCAL
        freopen("3177in.txt", "r", stdin);
    #endif

    while(scanf("%d", &n) && n)
    {
        int i;
        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]);
            R *= 3;
            while(L < R)
            {
                int mid = (L + R) / 2;
                if(test(mid))
                    R = mid;
                else
                    L = mid + 1;
            }
        }
        printf("%d
", L);
    }
    return 0;
}