Skip to content

14003: 【原4003】GetMinBottle

题目

题目描述

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

getMinBottles

Description

你有n个初始装水1L的瓶子。你可以将两个包含同样多水的瓶子合并为一个瓶子,水量为两个瓶子的和。 我希望最终剩下k个瓶子,但这可能是无法做到的。 但你还可以购进若干个初始装水1L的瓶子,这样就能通过上面的操作达到要求。 试问,最少需要购进多少个瓶子。

Input Format

一行两个正整数n,k (n<=100000000, k<=1000, 30%数据k=1)

Output Format

一行一个整数,表示最少需要购进多少个瓶子数

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;
}