题目链接
https://vjudge.net/problem/UVALive-3177
题目
Beijing was once surrounded by four rings of city walls: the Forbidden City Wall, the Imperial City
Wall, the Inner City Wall, and finally the Outer City Wall. Most of these walls were demolished in
the 50s and 60s to make way for roads. The walls were protected by guard towers, and there was a
guard living in each tower. The wall can be considered to be a large ring, where every guard tower has exaetly two neighbors.
The guard had to keep an eye on his section of the wall all day, so he had to stay in the tower.
This is a very boring job, thus it is important to keep the guards motivated. The best way to motivate
a guard is to give him lots of awards. There are several different types of awards that can be given:
the Distinguished Service Award, the Nicest Uniform Award, the Master Guard Award, the Superior Eyesight Award, etc.
The Central Department of City Guards determined how many awards have to
be given to each of the guards. An award can be given to more than one guard. However, you have
to pay attention to one thing: you should not give the same award to two neighbors, since a guard
cannot be proud of his award if his neighbor already has this award. The task is to write a program
that determines how many different types of awards are required to keep all the guards motivated.
Input
The input contains several blocks of test eases. Each case begins with a line containing a single integer
l ≤ n ≤ 100000, the number of guard towers. The next n lines correspond to the n guards: each line
contains an integer, the number of awards the guard requires. Each guard requires at least 1, and at
most l00000 awards. Guard i and i + 1 are neighbors, they cannot receive the same award. The first
guard and the last guard are also neighbors.
The input is terminated by a block with n = 0.
Output
For each test case, you have to output a line containing a single integer, the minimum number x of
award types that allows us to motivate the guards. That is, if we have x types of awards, then we can
give as many awards to each guard as he requires, and we can do it in such a way that the same type
of award is not given to neighboring guards. A guard can receive only one award from each type.
Sample Input
3
4
2
2
5
2
2
2
2
2
5
1
1
1
1
1
0
Sample Output
8
5
3
题意
有n个人围成一个圈，其中第i个人想要ri个不同的礼物。要求相邻的人的礼物不同。
问至少需要多少礼物？
分析
当n为偶数时，答案为max（r[i]+r[i+1]),1<=i<=n.
既然是一个圈，那么谁是第一号就无所谓了。而至少需要 r[1]+r[2] 个礼物才能使一、二号满足要求。
当n为奇数时，上述结论显然不成立，随便代入一个样列即可试出来。
我们可以二分答案p。
将p个礼物分成两部分，左边r[1]个，右边p-r[1]个。号码为奇数的人尽量从右边拿礼物，号码为偶数的人尽量从左边拿礼物，并用left[i]和right[i]来表示第i个人从左边和右边拿的礼物数。最后通过判断第n个人是否从左边拿了礼物来确定答案p是否合理。
代码
#include <iostream>
#include <cstdio>using namespace std;
const int maxn=1e5+100;
int n;
int lft[maxn],rght[maxn],r[maxn];bool ok(int p)
{int x=r[1]; //左边备选数int y=p-r[1]; //右边备选数lft[1]=r[1];rght[1]=0;for(int i=2;i<=n;i++){if(i&1) //奇数{rght[i]=min(y-rght[i-1],r[i]);lft[i]=r[i]-rght[i];}else //偶数{lft[i]=min(x-lft[i-1],r[i]);rght[i]=r[i]-lft[i];}}return lft[n]==0;
}
int main()
{while(~scanf("%d",&n) && n){for(int i=1;i<=n;i++){scanf("%d",&r[i]);}r[n+1]=r[1];if(n==1){printf("%d\n",r[1]);continue; //特判}//如果是偶数int L=0,R=0;for(int i=1;i<=n;i++) L=max(L,r[i]+r[i+1]);//如果是奇数if(n&1){for(int i=1;i<=n;i++) R=max(R,r[i]*3);//二分答案求最小值while(L<R){int mid=(L+R)>>1;if(ok(mid))R=mid;elseL=mid+1;}}printf("%d\n",L);}return 0;
}