http://acm.hdu.edu.cn/showproblem.php?pid=5835
题意：t组数据，n个礼物，每种礼物的个数。每个桌子上都要放两种礼物，分别是特殊礼物和普通礼物，在n种礼物中的每一个，都既可以是普通礼物，也可以是特殊礼物。对特殊礼物没有要求，不能由空桌子，且相邻的桌子上放的普通礼物要是不相同的。
解析：贪心。每次选择与上一个礼物不相同，且当前个数最多的。与礼物的总数/2比较大小，最多不能超过礼物的总数/2
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <sstream> #include <string> #include <algorithm> #include <list> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <cstdlib> using namespace std; int a[15]; int main() { //freopen("in.txt","r",stdin); int T; int n; scanf("%d",&T); for(int t = 1; t <= T; t ++) { int maxn,sum = 0,id,last; scanf("%d",&n); for(int i = 0 ; i < n; i ++) { scanf("%d",&a[i]); sum += a[i]; } sum = sum / 2; int ans = 0; while(1) { bool flag = false; maxn = 0; for(int i = 0; i < n; i ++){ if(a[i] > maxn && last != i) { id = i; maxn = a[i]; flag = true; } } if(flag == false) { break; } a[id] --; last = id; ans ++; if(ans >= sum) break; } printf("Case #%d: %d\n",t,ans); } return 0; }