HDU5835 Danganronpa

　　2016 CCPC网络赛

　　题意：每桌放两个物品，分别作为特殊礼物和普通礼物，要求任意相邻桌的特殊礼物不同种类。现在给定n种物品的数量，求最多能布置多少桌。 - 原题链接

　　假设现在已经放了i-1种物品，记物品总数为sum，其中需要同类相邻物品有ret+1个。在放置第i种物品时处理三种情况：

• 若a[i]>=sum，则第i种物品一一插空，更新ret
• 若a[i]>=ret，先插空隔开同类相邻物品，剩余随意插空，更新ret为0
• 若a[i]<ret，先插空隔开相邻物品，更新ret

---

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=10+5;

int T, n, a[maxn];

int main()
{
    scanf("%d", &T);
    for(int TT=1; TT<=T; TT++)
    {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)    scanf("%d", &a[i]);
        sort(a+1, a+1+n);

        int sum=0, ret=0;
        for(int i=n; i>=1; i--)
        {
            if(a[i]>=sum)    ret=a[i]-1-sum;
            else if(a[i]>=ret)    ret=0;
            else    ret-=a[i];
            sum+=a[i];
        }
        printf("Case #%d: %d\n", TT, min(sum-ret, sum/2));
    }
    return 0;
}