# 14003: 【原4003】GetMinBottle

### 题目描述

author: sunnywkn 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4003

# getMinBottles

## Sample Input

``````4 1
``````

## Sample Output

``````0
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/16.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
unsigned n, k;
cin >> n >> k;

if (n <= k) {
cout << k - n << endl;
return 0;
}

unsigned count = 0;
for (unsigned j = 0; j < 32; ++j) {
if (n & (1U << j)) ++count;
}

unsigned ori = n;

for (unsigned i = 0; i < 32 && count > k; ++i) {
if (n & (1U << i)) n += 1U << i;
count = 0;
for (unsigned j = 0; j < 32; ++j) {
if (n & (1U << j)) ++count;
}
}

cout << n - ori << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cmath"
#include "cstring"
using namespace std;

long long val_num[50] = { 0 };

int main() {
long long n, k;
cin >> n >> k;

long long cnt = 0, num = 0;
for (long long temp = n; temp; temp >>= 1, ++num) {
if (temp & 1) {
++cnt;
val_num[num] = 1;
}
}
num = 40;
long long ans = 0;
if (k >= n) {
ans = k - n;
}
else if (k >= cnt) {
ans = 0;
}
else {
for (;;) {
long long a = 0, b = 0;
for (; a < num && val_num[a] == 0; ++a);
val_num[a] = 0;
for (; b < num && val_num[b] == 0; ++b);
val_num[b] = 0;
ans += (long long)(pow(2, b) - pow(2, a));
for (++b, ++val_num[b]; b < num; ++b) {
if (val_num[b] > 1) {
val_num[b] = 0;
++val_num[b + 1];
}
else
break;
}
//统计个数
int cur_cnt = 0;
for (int i = 0; i < num; ++i)
if (val_num[i])
++cur_cnt;
if (cur_cnt <= k) {
//ans += k - cur_cnt;
break;
}
}
}

cout << ans;

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
#include <cstdio>
#include <climits>

using namespace std;

int high_bit(unsigned long long x) {
int d = 31;
while (d > 0 && !(x & (1 << d))) --d;
return d;
}

int main() {
long long x; int k;
long long ans = 0;
cin >> x >> k;
if (k > x) {
cout << k - x << endl;
return 0;
}
for (int i = 0; i < k - 1; i++) {
if (x == 0) break; else {
x -= 1 << high_bit(x);
}
}
if (x != 0 && x > (1 << high_bit(x))) {
ans += (1 << (high_bit(x) + 1)) - x;
}
cout << ans << endl;
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
using namespace std;
int n,k,one,e,t,m,ans;
int main() {
cin>>n>>k;
m=n;
if (n<k) {cout<<k-n; return 0;}
for (;m>0;m>>=1)
if (m&1) one++;
if (k>=one) {cout<<0; return 0;}
for (e=1;t<=one-k;n>>=1,e<<=1){
if (n&1) t+=1;
else ans+=e;
}
cout<<ans+1;
return 0;
}
``````

## zqy2018's solution

``````#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int K;
ll n;
ll lowbit(ll x){
return x & (-x);
}
void init(){
n = read(), K = read();
}
int Count(ll x){
int res = 0;
while (x > 0) ++res, x -= lowbit(x);
return res;
}
void solve(){
ll ans = 0;
if (n <= K) {
printf("%lld\n", K - n);
return ;
}
while (Count(n) > K)
ans += lowbit(n), n += lowbit(n);
printf("%lld\n", ans);
}
int main(){
init();
solve();
return 0;
}
``````