题目链接: https://www.luogu.org/problemnew/show/P1582


 

题目描述

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

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

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


 

输入格式

一行两个正整数,N,K(1<=N<=2*10^9,K<=1000)。


 

输出格式

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


 

输入输出样例

输入 #1

3 1

输出 #1

1

输入 #2

13 2

输出 #2

3

输入 #3

1000000 5

输出 #3

15808


 

题意:

只有水容量相同的瓶子才可以倒在一起,初始瓶子水为1升,且瓶子无限大,问你给你 N 个瓶子,还需要几个瓶子才能使得最后还剩 K个有水的瓶子。


 

题解:

先考虑最后剩一个瓶子,那么开始肯定要  个瓶子,最后才可以倒成一个瓶子。如果开始给你N个瓶子,设还需要X个瓶子可以写成:  N + X = ,这样如果最后剩一个瓶子,那么可以让N构成最小的的X就是答案。那么最后如果剩 K 个瓶子呢? 可以这样想:最后剩K个瓶子,但可以把这K个瓶子看成独立的一个一个的瓶子,最后又变成最后剩一个瓶子的问题了,公式就可以写成:

N + X =  +  + ······ +  ,所以最后问题变成如何加上最小的X使得 N + X 可以拆成k个2的次方的形式,每个2的次方最终就会倒水倒成1。设 ans = N + X 其实最后就是让ans的二进制的1的个数小于等于 K 就好,因为大于K的话一定无法拆解成 K 个2的次方的形式,肯定多余K个,若果最后的答案的二进制的个数小于K个,那么最后就可以拆了,比如:

N = 13, K = 2 让你求X

N = 1 1 0 1, 先加0 0 0 1 => 1 1 1 0 ,在加 0 0 1 0  => 1 0 0 0 0  每次加最低位,保证尽可能慢慢扩大X(贪心),这时候就剩1个二进制位了,可以拆成 :  +  的形式。

补充小知识点:

1、__builtin_popcount(n) (前面俩下划线_)用于求计算n表示成二进制时有多少个1。(不需要任何头文件就可以使用)

2、n & (-n) 代表每次加上一个是最后一个1向前进位的大小,即求lowbit(n)。


 

AC代码:

 1 #include <iostream>
 2 using namespace std;
 3 
 4 //k为x的二进制中从最低位到高位连续零的长度,返回2^k大小
 5 int lowbit(int x){
 6     return x&(-x);
 7 }
 8 
 9 int main(){
10     int n,k,ans=0;
11     cin>>n>>k;
12     while(__builtin_popcount(n)>k){
13         ans+=lowbit(n);
14         n+=lowbit(n);
15     }
16     cout<<ans<<endl;
17     return 0;
18 }

 

参考:http://www.luyixian.cn/news_show_15344.aspx