【题解】LA 3177【Beijing Guards】

分析

如果$n$为偶数,那么答案就是相邻的两个人的$r$值之和的最大值,即$p=\max(r_i+r_{i+1})(i=1,2,…,n)$,规定$r_{i+1}=r_1$。
而$n$为奇数的情况比较烦,这个时候上二分答案,假设已知共有$p$种礼物,第$1$个人的礼物是$1$~$r_1$,显然最优分配策略一定是这样:编号为偶数的人尽量向前取,编号为奇数的人尽量向后取,最后判断编号为$1$的人和编号为$n$的人是否冲突即可。

代码

#include<cstdio>
#include<algorithm>
using std::max;using std::min;
const int MAXN = 100000 + 6;
int n,r[MAXN],left[MAXN],right[MAXN];

bool test(int p){
    int x = r[1],y = p - r[1];
    left[1] = x;right[1] = 0;
    for(int i = 2;i <= n;i++){
        if(i % 2 == 1) right[i] = min(y - right[i - 1],r[i]),left[i] = r[i] - right[i];
        else left[i] = min(x - left[i - 1],r[i]),right[i] = r[i] - left[i];
    }
    return left[n] == 0;
}

int main(){
    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 M = L + (R - L) / 2;
                if(test(M)) R = M;else L = M + 1;
            }
        }
        printf("%d\n",L);
    }

    return 0;
}