uva3177BeijingGuards

题意：有n个人围城一个圈，其中第i个人想要ri个不同的礼物，相邻的两个人可以聊天，炫耀自己的礼物，如果两个相邻的人拥有同一种礼物，则双方都会很不高兴。问：医用需要多少种礼物才能满足所有人的需要？假设每种礼物有无穷多个，不相邻的两个人不会一起聊天。

分析：《训练指南》上的分析我没看懂，但是我觉得书上讲的麻烦了。当输入完每个人的ri后，统计相邻两个人的ri之和的最大值Max，如果这个Max比应当提供给所有人礼物数的均值的两倍还要少，那么ans=均值的两倍，否则ans=Max，代码写起来也很短：

#include <stdio.h>
#include <iostream>
using namespace std;
const int MAXN = 100000 + 10;
int a[MAXN];
int main(){
    int n, i, j;
    while(scanf("%d", &n)!=EOF&&n){
        int sum =0, Max=0;
        for(i=0; i<n; i++) scanf("%d", &a[i]);
        for(i=0; i<n; i++){
            sum+=a[i];
            j=i+1;
            if(j==n) j=0;
            if(Max<a[i]+a[j]) Max=a[i]+a[j];
        }
        int tmp=(sum-1)/(n/2)+1;
        if(Max<tmp)Max=tmp;
        printf("%d\n", Max);
    }
    return 0;
}