SRM439 Div.1 Easy PouringWater

方針

N本のボトルを運ぶときの最小の本数==Nの立っているビットの数
なので、ビットカウントをしてそれがKより少なければ運ぶことができる。

これを1本ずつ足していって調べてみればよい。
足す本数は、多く見積もっても2^k < 10^7 < 2^(k+1)となるような2^kであって
ビットカウントにO(logn)掛かるとしてもO(nlogn)で間に合う。

• 任意の数を2の冪乗和で表すときの要素数の最小==立っているビットの数

当たり前なのに使えていなかったので反省したい。

以下ソース

    int cbit(int arg){
        int ret=0;
        while(arg){
            if(arg & 1) ret++;
            arg >>=1;
        }
        return ret;
    }

    int getMinBottles(int N, int K) {
        for(int i=0;;i++){
            if(cbit(N+i) <= K){
                return i;
            }
        }
        return -1;
    }