题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5835
题意：有n种礼物，每个有ai个，现在开始给每个人发礼物，每人一个普通礼物和神秘礼物，相邻两人的普通礼物必须不同，每个礼物都可以作为神秘礼物/普通礼物，问最多可以发给多少人。
思路：当n为1，那么答案为1。如果有两种以上的礼物，我们现在只看数量最多的礼物A和B，A>B，我们可以这么放ABABABAB..如果A足够多，那么可以变成ABABAB..A，此时B用完了，但是A还有剩余，我们接着放其他的，这时候发现，没放一个其他的礼物就可以再放一个A礼物。如果A礼物足够多，我们可以发给(sum-A)+(sum-A)+1这么多人，(sum-A)是非A礼物的数量，(sum-A)+1是A的数量。如果A不够多（神秘礼物都不够发了），那么答案就是sum/2。两个中取最小值就是答案。
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;i++) #define Rrep(i,j,k) for (int i=j;i>=k;i--) #define Clean(x,y) memset(x,y,sizeof(x)) #define LL long long #define ULL unsigned long long #define inf 0x7fffffff #define mod 100000007 int T,n; int a[100]; int main() { cin>>T; rep(kase,1,T) { scanf("%d",&n); rep(i,1,n) scanf("%d",&a[i]); sort(a+1,a+1+n); int sum = 0; rep(i,1,n) sum+=a[i]; int ans = sum/2; ans = min( ans , (sum-a[n])*2+1 ); printf("Case #%d: %d\n",kase,ans); } return 0; }
