https://vjudge.net/problem/UVA-1335
！！！！！：不要去uvalive提交，数据是炸的
题意：
有n个守卫围成一圈，他们每个人想要一定数量的礼物，但是相邻的两人的礼物必须完全不同，问最少需要多少种礼物。
思路：
当n为1，直接输出；
当n为偶数时，可以想到取相邻之和的最大值，可以避免冲突，奇数编号的尽量往前取，偶数编号的尽量往后取，那么第一个和第n个就是取的不同的一端，自然不会冲突；
当n为奇数时，为了避免第一个和第n个冲突，就让第一个尽量往前取，第n个尽量往后取，那么贪心的策略就出来了，除了第一个以外的，奇数编号尽量往后取，偶数编号的尽量往前取，就达到了使得第一个和第n个冲突少的目的。之后用二分找答案，在记录取的时候，只需要记录在前面取了都少个，后面取了多少个，而不需要具体记录取了哪几种。
代码：
1 #include2 #include 3 #include 4 using namespace std; 5 6 int ne[100005]; 7 int qian[100005];//表示在前面取的个数 8 int hou[100005];//后面取的个数 9 int n;10 11 bool meet(int an)12 {13 int x = ne[1],y = an - ne[1];14 15 qian[1] = x,hou[1] = 0;16 17 for (int i = 2;i <= n;i++)18 {19 if (i % 2)20 {21 hou[i] = min(y - hou[i-1],ne[i]);//奇数尽量往后取，在前一个取剩下的当中取22 qian[i] = ne[i] - hou[i];//不够的再在前面取23 }24 else25 {26 qian[i] = min(x - qian[i-1],ne[i]);//同理27 hou[i] = ne[i] - qian[i];28 }29 }30 31 return qian[n] == 0;//表示第n个没有在前面取，就与第一个没有冲突32 }33 34 int main()35 {36 while (scanf("%d",&n) != EOF && n)37 {38 for (int i = 1;i <= n;i++) scanf("%d",&ne[i]);39 40 ne[n+1] = ne[1];41 42 if (n == 1)43 {44 printf("%d\n",ne[1]);45 46 continue;47 }48 49 if (n % 2 == 0)50 {51 int ans = 0;52 53 for (int i = 1;i <= n;i++)54 ans = max(ne[i]+ne[i+1],ans);55 56 printf("%d\n",ans);57 }58 else59 {60 int l = 0,r = 0;61 62 for (int i = 1;i <= n;i++)63 {64 l = max(ne[i] + ne[i+1],l);65 r = max(ne[i]*3,r);66 }67 68 while (l < r)69 {70 int mid = (l + r) / 2;71 72 if (meet(mid)) r = mid;73 else l = mid + 1;74 }75 76 //while (r - 1 >= 0 && meet(r-1)) r--;77 78 printf("%d\n",r);79 }80 }81 82 return 0;83 }