题意：有n个人为成一个圈，其中第i个人想要r[i]种不同的礼物，相邻的两个人可以聊天，炫耀自己的礼物。如果两个相邻的人拥有同一种礼物，则双方都会很不高兴，问最少需要多少种不同的礼物才能满足所有人的需求，假设每种礼物有无限多个。 n<=100000
题解:
对于n==1 直接输出a[1]
对于n是偶数，找相邻两个和的最大值
对于n是奇数，现在假设有m个奖品，1号放1---a[1]，2号开始的偶数号都尽量放小的
奇数都尽量放大的，尽量的意思就是避开前一个的范围就好。
于是我们二分m这个值就好
1 #include<bits/stdc++.h> 2 #define N 100005 3 using namespace std; 4 int n,a[N],rr[N],ll[N],st,ed; 5 int ans,l,r; 6 int main() 7 { 8 while (scanf("%d",&n)!=EOF && n!=0) 9 { 10 memset(a, 0, sizeof(a)); 11 int why=0; 12 for (int i=1;i<=n;i++) 13 { 14 scanf("%d",&a[i]); 15 why=max(why,a[i]*3); 16 } 17 if (n==1) 18 { 19 printf("%d ",a[1]); 20 continue; 21 }else 22 if (n%2==0) 23 { 24 ans=a[1]+a[n]; 25 for (int i=2;i<=n;i++) 26 ans=max(ans,a[i]+a[i-1]); 27 printf("%d ",ans); 28 }else 29 { 30 r=why+1; 31 l=a[1]+a[n]; 32 for (int i=2;i<=n;i++) 33 l=max(l,a[i]+a[i-1]); 34 while (l<r) 35 { 36 int mid=(l+r)/2; 37 st=a[1]; 38 ed=mid-a[1]; 39 ll[1]=st; 40 rr[1]=0; 41 for (int i=2;i<=n;i++) 42 { 43 if (i%2==1) 44 { 45 rr[i]=min(ed-rr[i-1],a[i]); 46 ll[i]=a[i]-rr[i]; 47 }else 48 { 49 ll[i]=min(st-ll[i-1],a[i]); 50 rr[i]=a[i]-ll[i]; 51 } 52 } 53 if (ll[n]==0) r=mid;else l=mid+1; 54 } 55 printf("%d ",l); 56 } 57 } 58 return 0; 59 }