(Sky OJ) 26. G.雷精靈的煩惱(互動題)

https://pc2.tfcis.org/sky/index.php/problem/view/26/

最naive的做法就是：把每個數值找出來之後，看看不見的是哪一個就okay了！

但是，仔細想想，假設你今天只focus在第一個bit，你會發現，這個bit是0的數字們的數量 跟 這個bit是1的數字們的數量 相差最多是1！從中，你就可以發現不見的bit是0還是1。

那，得到這個之後，我們就不用再檢查所有的數字了！只需要檢查上面找到的兩堆數字中，size比較小的那堆 (可以想想看為甚麼)。

這樣需要的次數就是O(N) + O(N/2) + O(N/4) + ....... = O(2N)

#include <iostream>
#include <stdio.h>
#include <vector>
#include "Pikachu.h"
using namespace std;

int main () {
    int n=Init();
    vector<int> v;
    for (int i=0;n-1>i;i++) v.push_back(i+1);
    int bit=-1;
    int ans=0;
    while (v.size() != 0) {
        bit++;
        vector<int> _[2];
        for (int i:v) {
            if (GetBit(i,bit) == 1) _[1].push_back(i);
            else _[0].push_back(i);
        }
        if (_[0].size() > _[1].size()) {
            v=_[1];
            ans += (1<<bit);
        }
        else {
            v=_[0];
        }
    }
    Answer(ans);
}