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

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

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

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

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

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

 

1 //#define LOCAL 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std;  6  7 const int maxn = 100000 + 10; 8 int n, r[maxn], left[maxn], right[maxn]; 9 10 bool test(int p)11 {12     int x = r[1], y = p - x;13     left[1] = x; right[1] = 0;14     for(int i = 2; i <= n; ++i)15     {16         if(i & 1 == 1)17         {
    //奇数尽量往后取18             right[i] = min(r[i], y - right[i-1]);19             left[i] = r[i] - right[i];20         }21         else22         {
    //偶数则尽量往前取23             left[i] = min(r[i], x - left[i-1]);24             right[i] = r[i] - left[i];25         }26     }27     return (left[n] == 0);28 }29 30 int main(void)31 {32     #ifdef LOCAL33         freopen("3177in.txt", "r", stdin);34     #endif35 36     while(scanf("%d", &n) && n)37     {38         int i;39         for(i = 1; i <= n; ++i)40             scanf("%d", &r[i]);41         if(n == 1)42         {43             printf("%d\n", r[1]);44             continue;45         }46         int L = 0, R = 0;47         r[n+1] = r[1];48         for(i = 1; i <= n; ++i)49             L = max(L, r[i]+r[i+1]);50         if(n%2 == 1)51         {52             for(i = 1; i <= n; ++i)53                 R = max(R, r[i]);54             R *= 3;55             while(L < R)56             {57                 int mid = (L + R) / 2;58                 if(test(mid))59                     R = mid;60                 else61                     L = mid + 1;62             }63         }64         printf("%d\n", L);65     }66     return 0;67 }