UESTC - 86 Divide （二进制贪心模拟）

二进制优化的原理，是二进制的自相似性和问题流程的自相似性。
说起来很抽象。

这道题吧，超级厉害的，我一开始做的时候思路理不清楚，这个题最不好弄的，一是我最开始算复杂度的时候算的不对，二是二进制减法那个地方

网上我搜到的题解都讲得不是很清楚，结果我自己想写的时候，发现这个问题是很难描述。
想完整的介绍思想，理清思路还有一点难。

这个题背后的问题和涉及的思想还是很厉害的，怎么描述呢。进制是具有一种自相似的特性的。
http://www.bilibili.com/video/av7398130/
这个视频中对进制的描述会给你一些启发，我就是从这里面得到的启发；
这个问题是给出二进制每一位上代表的数值的个数，让我们把数值分为两堆，使两堆之间差值最小；
偶数可分，奇数不可分；
可分的部分不是问题，问题是不可分的部分，而不可分的部分的最大位是最大的问题，所以这个题的解决方案就是先进位处理，标记进位过的位，再寻找最大的不可分的，未进位的位，再用这个位上的值，减去他的低位的值的和就是最小的差值；

我说的大概还是有点抽象吧，其实这个问题，做个动态视频模拟就很好理解了；
还有就是这个题的二进制减法很有意思；

bool flag = false;
        for(int i=0;i<=Max;i++)
        {
            if(flag)  num[i] ^= 1;
            else if(num[i]) flag = true;
        }

喵喵喵？
比如10000-1110 ，可以拆分为1 + 1111 - 1101 else if(num[i]) flag= true；这个操作一方面是在寻找那个最小的不为0位，一边巧妙地利用flag实现+1。（啰嗦一下：如最小不为0位为1，那么异或值为0这一位跳过不处理正好实现+1）
那么此时只要利用异或（^）的特性，按位异或的作用使求出每一位的差的绝对值。1111-1101按位的差值的绝对值必然为总的差值

啊，差不多写完了，感觉我的意思表达的还不是很清楚，大概是太菜了吧

#include<stdio.h>
#include<string.h> 
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;

long long num[101000];
bool vis[101000];
 
int main()
{
    int t,cas = 1;
    scanf("%d",&t);
    while(t--)
    {
        memset(num,0,sizeof(num));
        memset(vis,0,sizeof(vis));
        int n;
        scanf("%d",&n);
        while(n--)
        {
            int a,b;
            scanf("%lld%lld",&a,&b);
            num[a] += b;
        }
        
        for(int i=0;i<101000;i++)
        {
            if(num[i]>=2)
            {
                num[i+1]+=num[i]>>1;
                num[i] = num[i]&1;
                vis[i+1] = true;
            }
        }
        int Max = -1;
        for(int i=100999;i>=0;i--)
        {
            if(num[i]&1 && !vis[i])
            {
                Max = i;
                break;
            }
        }
        bool flag = false;
        for(int i=0;i<=Max;i++)
        {
            if(flag)  num[i] ^= 1;
            else if(num[i]) flag = true;
        }
        printf("Case #%d: ",cas++);
        flag = false;
        for(int i=max(0,Max);i>=0;i--)
        {
            if(num[i])  flag = true;
            if(flag || i==0)  printf("%lld",num[i]);
        }
        printf("\n");
    }
}