题目链接
题意：可能我感觉题我都读了两遍了，还感觉我是不是，题意理解错了，因为当时很蒙，所以也是没有思路，我就没有做这道题，后来我没有看队友A了，我就感觉应该不难吧，就是n种礼物，每种礼物就a[i]个，让满足每个人都有一个神秘礼物和普通礼物，并且相邻的桌子上不能放同一种的礼物，神秘礼物没限制，礼物是连续的放的，问最多可以有所少人得到礼物。
思路：我们可以很容易的发现，很多结果都是sum/2,但是并不是都是，结果的最大值是sum/2,这题是贪心的思想，我们这样来看吧，我们把数量最多的那种礼物，先当成是普通的礼物，放在桌子上，中间隔着其他的礼物，根据规律呢，我们可以发现最大数量的那个礼物如果大于其他礼物数量之和的话，我们先把最大数量的礼物和其他的礼物间隔的排，直到其他礼物没有，如果最大礼物排完不够填充为神秘礼物，那结果就是sum/2,否则的话就是（sum-最大数量的礼物+1）+（sum-最大数量的礼物），如果最大数量的礼物小于等于其他数量礼物的和，直接输出sum/2,
代码
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; int main() { int n,t,a[17]; cin>>t; int cnt=1; while(t--) { cin>>n; int sum=0; for(int i=0; i<n; i++) { cin>>a[i]; } if(n==1) { if(a[0]>=2) printf("Case #%d: 1\n",cnt++); else printf("Case #%d: 0\n",cnt++); } else { int m=0,v,maxn; int flag=0; sort(a,a+n,greater<int>()); for(int i=1;i<n;i++) { sum+=a[i]; } if(a[0]>sum) { v=sum+1; if(a[0]>=v) { if(a[0]>(2*v+sum)) maxn=v+sum; else flag=1; } } else { flag=1; } if(flag) printf("Case #%d: %d\n",cnt++,(sum+a[0])/2); else printf("Case #%d: %d\n",cnt++,maxn); } } return 0; }