n为偶数的时候比较简单，就是相邻两个守卫的礼物和的最大值。
首先这是个下限，其次这个值也满足题目要求，所以这就是答案了。
当n为奇数的时候上限是守卫索要礼物的最大值的三倍。
这也很容易理解，比如n=5，r都为1的时候，每个人拿到的礼物是1,2,1,2,3
有了上限有了下限就可以二分找出答案来了。
test函数的作用就是测试p种礼物能否满足要求。
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
int n, r[maxn], left[maxn], right[maxn]; bool test(int p)
{
int x = r[], y = p - x;
left[] = x; right[] = ;
for(int i = ; i <= n; ++i)
{
if(i & == )
{//奇数尽量往后取
right[i] = min(r[i], y - right[i-]);
left[i] = r[i] - right[i];
}
else
{//偶数则尽量往前取
left[i] = min(r[i], x - left[i-]);
right[i] = r[i] - left[i];
}
}
return (left[n] == );
} int main(void)
{
#ifdef LOCAL
freopen("3177in.txt", "r", stdin);
#endif while(scanf("%d", &n) && n)
{
int i;
for(i = ; i <= n; ++i)
scanf("%d", &r[i]);
if(n == )
{
printf("%d\n", r[]);
continue;
}
int L = , R = ;
r[n+] = r[];
for(i = ; i <= n; ++i)
L = max(L, r[i]+r[i+]);
if(n% == )
{
for(i = ; i <= n; ++i)
R = max(R, r[i]);
R *= ;
while(L < R)
{
int mid = (L + R) / ;
if(test(mid))
R = mid;
else
L = mid + ;
}
}
printf("%d\n", L);
}
return ;
}
代码君