2017广东工业大学程序设计竞赛决赛-倒水(Water)(二进制的奇妙运用)

    xiaoxiao2021-03-25  7

    倒水(Water)

    Description

    一天,CC买了N个容量可以认为是无限大的瓶子,开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了,于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子,把一个瓶子的水全部倒进另一个里,然后把空瓶丢弃。(不能丢弃有水的瓶子)

    显然在某些情况下CC无法达到目标,比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限,开始时有1升水),以到达目标。

    现在CC想知道,最少需要买多少新瓶子才能达到目标呢?

    Input

    第一行一个整数T,表示有T组数据。

    接着T每行两个正整数, N,K(1<=N<=10^9K<=1000)

    Output

    一个非负整数,表示最少需要买多少新瓶子。

    Sample Input

    33 113 21000000 5

    Sample Output

    1315808

    HINT

    解题思路:对于 n 瓶一升的水,把他们合并后最少的瓶子数为 n 的二进制中 1 的个数。假设 n 的二进制中 1 的个数大于 k,那么我们要找到 1 个大于 n 的数,且二进制中 1 的个数等于k的最小的数 m,那么答案为 m-n。假设 n 二进制中,最右边的 1 在第 i 位(这里的第几位是从右往左数的,最右边为第 0位),如果加上一个2^i,则结果二进制中 1 的个数必定不会增加。所以只需要一直加上一个 2^i,直到结果中 1 的个数等于 k 即可

    #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <functional> #include <climits> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int get(LL x) { int sum=0; while(x) { if(x&1) sum++; x>>=1; } return sum; } int main() { int k; LL n,ans; int t; scanf("%d",&t); while(t--) { scanf("%lld%d",&n,&k); ans=0; while(get(n)>k) { LL i; for(i=1;;i<<=1) if(n&i) break; ans+=i; n+=i; } printf("%lld\n",ans); } return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-200157.html

    最新回复(0)