2018CCPC吉林C-JUSTICE（思维模拟）

Put simply, the Justice card represents justice, fairness, truth and the law. You are being called to account for your actions and will be judged accordingly. If you have acted in a way that is in alignment with your Higher Self and for the greater good of others, you have nothing to worry about. However, if you have acted in a way that is out of alignment， you will be called out and required to own up to your actions. If this has you shaking in your boots, know that the Justice card isn't as black and white as you may think.

On the table there are n weights. On the body of the i-th weight carved a positive integer ki, indicating that its weight is gram. Is it possible to divide then weights into two groups and make sure that the sum of the weights in each group is greater or equal to 1/2 gram? That's on your call. And please tell us how if possible.

输入

In the first line of the input there is a positive integer T (1≤T≤2000), indicating there are T testcases.
In the first line of each of the T testcases, there is a positive integer n (1≤n≤105 , Σn≤7 × 105 ),indicating there areηweights on the table.
In the next line， there are n integers ki (1≤ki≤109), indicating the number carved on each weight.

输出

For each testcase, first print Case i : ANSWER in one line, i indicating the case number starting from 1 and ANSWER should be either YES or NO, indicating whether or not it is possible to divide the weights. Pay attention to the space between : and ANSWER.
If it's possible, you should continue to output the dividing solution by print a 0/1 string of length n in the next line. The i-th character in the string indicating whether you choose to put the i-th weight in group 0 or group 1.

样例输入

样例输出

Case 1: NO
Case 2: YES
001
Case 3: YES
10

题意：给你n个数，能否分成两组，使每组的2的ki次方分之一的和大于等于二分之一，能的话输出分组方案

思路：不难发现, 例, 也就是2个k能合成一个k/2,

能不能分成两组，只需要看最后合完之后1的个数是不是大于等于2

分组方案怎么确定？这个1要么是原来的1，要么是合成之后的1.

如果是原来就有的1，那么它自己一组，其他的一组，符合题意

如果是合成的1，那么我们找一下它是由哪几个ki合成的，这些ki一组，其他的一组，符合题意

我们需要记录输入中每一个数出现了多少次，但是数最大是1e9，直接用数组记录很明显开不了。

因为数据最多是1e5个，我们来想1e5个数据能分成两组的最坏情况（两组都是二分之一，每个数都被用到），那么数据应该是

1,2,3,4，……1e5-1，1e5-1（除了1e5-1是两次，其他的都只出现1次）

所以大于等于1e5的数据其实对于判断是没有影响的，这些数我们可以不管

这样只需要开1e5的数组就可以了

1组：和刚好为二分之一

0组：其他

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#define ll long long
using namespace std;
const int maxn=1e5+6;
const int TT=1e5;
int a[maxn],ans[maxn],vis[maxn];
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int main()
{
    int T,t=1;
    scanf("%d",&T);
    while(T--) {
        int n;
        scanf("%d",&n);
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        int up=0;//上界
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>TT) continue;
            vis[a[i]]++;
            up=max(up,a[i]);
        }
        ll p=0;
        for(int i=up;i>1;i--){
            p=(p+vis[i])/2; //p是指后面的数能提供多少个（i-1）
        }
        if(vis[1]+p>=2){//原有的1的个数加上后面合成提供的1的个数>=2,YES
            printf("Case %d: YES\n",t++);
            ll cnt=0;
            for(int i=1;i<=20;i++){  //这里这个20也可以改成up
                ll temp=ksm(2,i-1);  //这样不会爆吗？不会，只要能合成1,那么他会在20之前跳出循环，
                                     //2的17次方超1e5，所以在i到18之前肯定能合成1个指数1
                                     //用20做上界或者up做上界无影响
                if(vis[i]+cnt>=temp){//需要temp个i,原有的i加上分解出来的i的数目>=需要的
                    ans[i]=temp-cnt; //对于原有的i我们需要的数目是需要的减去前面分解提供的
                    break;           //第一组（和刚好为二分之一）找完了，跳出循环
                }
                else{                //不够
                    cnt=(cnt+vis[i])*2;//一个i提供两个（i+1）给后面
                    ans[i]=vis[i];//全用
                }
            }
            for(int i=0;i<n;i++){
                if(a[i]>TT) printf("0");//大于TT的分在0组里（我觉得分在1组里也没有影响，但是会wa，QAQ）
                else{
                    if(ans[a[i]]){
                        printf("1");
                        ans[a[i]]--;
                    }
                    else printf("0");
                }           
            }
            printf("\n");   
        }
        else printf("Case %d: NO\n",t++);
    }
    return 0;
}