1.题目描述:点击打开链接
2.解题思路:本题是一道思维题。这种题一般需要先自己在演草纸上多尝试几种情况，并总结出一般的规律解决。尝试后，可以发现，如果n为偶数时，那么结果就是max{r[i]+r[i+1]}（规定r[n+1]=r[1]）。如果n为奇数时，上述方法不再奏效。这个时候需要利用二分查找，假设共有p种礼物，设第一个人的礼物是1~r[1]。不难发现最优解的策略一定是这样的：如果i为偶数，那么他尽量靠前取数，如果i为奇数，那么他尽量靠后取数。这样，最后检验一下第n个人和第1个人是否冲突即可。例如，n=5,A={2,2,5,2,5},p=8时，则按照上面策略，第1个人取{1,2}，第2个人取{3,4}，第3个人取{8,7,6,5,2}，第4个人取{1,3}，第5个人取{8,7,6,5,4}。此时发现第5个人和第1个人不冲突，所以p=8可行。
本题有一个很好的技巧：由于不要求输出每个人的选取方案，因此可以把这p种礼物分为两段考虑，即1~r[1]和r[1]+1~p。用数组Left[i]表示第i个人在第一段中取走的个数，Right[i]表示第i个人在第二段中取走的个数。这样，按照上述策略，，最后只用看Left[n]==0是否成立即可（因为第一个人拿走了第一段中的所有数，要想不冲突，第n个人在第一段中不能取走任何数）。具体细节详见代码注释。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 100000+10int r[N];int Left[N], Right[N];//Left[i]表示第i个人在1~r[1]范围之间拿的个数，Right[i]表示第i个人在r[1]+1~n之间拿的个数int n;bool test(int p){int x = r[1], y = p – r[1];Left[1] = x;//第1个人拿走1~r[1]的所有数Right[1] = 0;for (int i = 2; i <= n; i++)if (i & 1){Right[i] = min(y – Right[i – 1], r[i]);//尽量拿右边的东西，要在右边剩余的个数和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(){//freopen("t.txt", "r", stdin);while (~scanf("%d", &n) && 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]);//L先设为r[i]+r[i+1]的最大值，便于合并n为奇数，偶数两种情况if (n & 1){for (int i = 1; i <= n; i++)R = max(R, r[i] * 3);//R的范围尽量设的大一些，选取为r[i]*3while (L < R){int M = L + (R – L) / 2;if (test(M))R = M;//由于是找最小值，因此如果M可以，那么ans≤M，否则ans>Melse L = M + 1;}}printf("%d\n", L);}return 0;}
那段岁月，无论从何种角度读你，你都完美无缺，
