题意：有n个人围城一个圈，其中第i个人想要ri个不同的礼物，相邻的两个人可以聊天，炫耀自己的礼物，如果两个相邻的人拥有同一种礼物，则双方都会很不高兴。问：医用需要多少种礼物才能满足所有人的需要？假设每种礼物有无穷多个，不相邻的两个人不会一起聊天。
分析：《训练指南》上的分析我没看懂，但是我觉得书上讲的麻烦了。当输入完每个人的ri后，统计相邻两个人的ri之和的最大值Max，如果这个Max比应当提供给所有人礼物数的均值的两倍还要少，那么ans=均值的两倍，否则ans=Max，代码写起来也很短：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4 const int MAXN = 100000 + 10; 5 int a[MAXN]; 6 int main(){ 7 int n, i, j; 8 while(scanf("%d", &n)!=EOF&&n){ 9 int sum =0, Max=0; 10 for(i=0; i<n; i++) scanf("%d", &a[i]); 11 for(i=0; i<n; i++){ 12 sum+=a[i]; 13 j=i+1; 14 if(j==n) j=0; 15 if(Max<a[i]+a[j]) Max=a[i]+a[j]; 16 } 17 int tmp=(sum-1)/(n/2)+1; 18 if(Max<tmp)Max=tmp; 19 printf("%d\n", Max); 20 } 21 return 0; 22 }
