SRM 439 DIV1 Easy - PouringWater (復習○)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10408&rd=13747

N個のボトルがあり、最初は1Lだけ水が入っている。
ここで同じ量だけ水が入っているボトルを選んで、一つのボトルに水をまとめることができる。
このとき、水が入っているボトルをK個以下にしたい。
ただし現在のボトル数ではK個以下にできない場合は、ボトルを追加で買うことができる。

このとき、水が入っているボトルをK個以下にしたいときに、追加で必要なボトルの最小数を求める。

解き方


ぱっと見た感じだと解法が思い浮かばないので、ボトル数の計算を式に落とせないか考えてみる。
ここで、1個、2個、4個、8個・・・のボトルは一つにまとめられることから
2^K個のボトルは1つにまとめることができる。

次に例をあげてみると、
15=2^3++2^2+2^1+1のように変換することができる。

上記の式を眺めてみると、ボトルの数は2進数に変換したときの1の数と等しい
ことがわかる。

次にボトルを減らしたいときに買うべきボトルの数を、先の例を使って考える。
15=1111であり、ボトルを1つ買うと
10000、つまりボトルが1つになる。

つまり、右から走査し1が存在した時はその数を足し、
ボトル数がK個以下になるまで繰り返してあげればよい。

コード


#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class PouringWater {

public:

int calc(int x){
int ret=0;
while(x>0){
ret+=x%2;
x/=2;
}
return ret;
}

int getMinBottles(int N, int K) {
int ret=0;

while(calc(N)>K){
for(int i=0;i<32;i++){
if(N&(1<<i)){
ret+=(1<<i);
N+=(1<<i);
break;
}
}
}

return ret;
}

};
このエントリーをはてなブックマークに追加