CONTINUE...? ZOJ

CONTINUE...?

ZOJ - 4033

题解：先计算一下总数sum是否是偶数，如果不是则不能分出来，如果是则从后面开始分，先把人分到1、3组，分完sum / 2这些人，如果恰好能够分成零，那么剩下前面的都分到2、4组就可以了。如果不能，那么就把当前剩下的它需要的x能够凑成sum/2，将x这个地方的人分到1、3组。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll maxn = 100005;
char a[maxn];
ll b[maxn];
int main()
{
    ll t,n,i,j;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld %s",&n, a + 1);
        ll sum = (n * (n + 1)) / 2;
        if(sum % 2 != 0)
        {
            printf("-1
");
            continue;
        }
        memset(b,0,sizeof(b));
        sum  = sum / 2;
        for(i = n; i >= 1; i --)
        {
            if(sum >= i)
            {
                sum -= i;
                if(a[i]  == '0')
                    b[i] = 1;
                else
                    b[i] = 3;
                if(sum == 0) break;
            }
            else{
                if(a[sum] == '0') b[sum] = 1;
                else b[sum] = 3;
                break;
            }
        }
        for(i = 1; i <= n; i ++)
        {
            if(b[i] == 0)
            {
                if(a[i] == '0')
                    printf("2");
                else
                    printf("4");
            }
            else printf("%lld",b[i]);
        }
        printf("
");
    }
    return 0;
}