杯子 (位运算)

杯子 (位运算)"/>

杯子 (位运算)

小明买了 n个容积可以是无穷大的杯子，刚开始的时候每个杯子里有 1 升水，接着小明发现杯子实在太多了，于是他决定保留不超过 k个杯子。每次他选择两个当前含水量相等的杯子，把一个杯子的水全部倒进另一个里，然后把空瓶丢弃。（不能丢弃有水的杯子）

显然在有些情况下小明无法达到他的目标，比如 n=3，k=1。此时小明会重新买一些新的杯子（新杯子容积无限，开始时有 1 升水），以达到目标。

现在小明想知道，最少需要买多少个新杯子才能达到目标呢？

输入格式

一行两个正整数，n，k。

输出格式

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

数据范围

对于 50% 的数据，1≤n≤10000000

对于 100% 的数据，1≤n≤1000000000 , k≤1000

Sample 1

3 1

1

Sample 2

13 2

3

Sample 3

1000000 5

15808

题解:

当 n = 10时, 10个杯子可变为5个杯子 , 5 个杯子可以变为3个(将5分为1和4 , 4 再 除2)

3个又可再变为2(之前的2再除2再加上剩余的1个杯子) ;

由以上分析可知 : n 个 杯子 可 变为 n/2 个 或 1 + (n - 1) / 2 个 ;

1 + (n - 1) / 2 当中的 1 可以从位运算的角度考虑 ;

例如n = 10 , 二进制表示为 1010 , 当可以整除2时 , 意味着第0位为0 , 每次进行除2操作 , 相当于

n >> 1 , 当第0位为1时 , 不能整除 , 此时上式的1就出来了 

由此可知 , n 个杯子最终能化简到多少个杯子取决 n 的二进制中 1 的个数 ; 

因此 , 题目结果可以分成两种情况 : 

1. n当中1的个数 <= k , 此时 不用 购买新的杯子 ;

2. n当中1的个数 > k , 那么此时只需要将 n 当中多余 的1  消去即可 ;

例1 : n = 13 , 二进制为 : 1101 , k = 2 时:

第一步 : 加上二进制 1 ---> 1110 ( 此时1的个数仍大于 k)

第二步: 加上二进制10 --->10000 ( 此时结束 ) ;

例2 : n = 111011011101 ( 二进制 )  k = 4 时 :

1. 加上 1 , --> 111011011110 ;

2. 加上10 ---> 111011100000 ;

3. 加上 100000  ---> 111100000000 ;

因此 第一步总是先加上最右边的 1 , 并且标记好原来的 n 上 哪一位是1 ;

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include<vector>using namespace std;int n , k ;
vector<int> one;
int st[50] ;int main()
{	cin >> n >> k ;int cnt = 0 ;// 用于记录下标while(n){if(n % 2) {one.push_back(cnt) ; //存所有1的下标st[cnt] = 1 ; // 用于记录当前位需不需要加1}cnt++ ;n /= 2 ;}int ans = 0 ;if(k < one.size()) //如果n当中1的个数大于k{ans += 1 << one[0] ;//首先加上最右边的1 ;for(int i = one[0] + 1 ; i < one[one.size() - k] ; i++){//one[one.size() - k] 表示保留左边的k-1个 1 ,其余消去//例如 11100110 , k = 4时, 只用消去最右边的两个1 , 消去的意思时将多余的1变为1个1if(st[i] == 0)ans += 1 << i ; //判断是否要加上}}cout << ans ;return 0;
}