题目描述

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

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

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

输入输出

输入格式：

一行两个正整数， N,K(1≤N≤2e9,K≤1000 )。

输出格式：

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

样例

分析：
显然与二进制有关，我们最后的ans一定是k个2的幂次相加最接近n的最小值，考虑从最后往前的第一个1开始加起，直到1的个数等于k为止。
ps：最后一个1为x^-x
代码：

 #include"bits/stdc++.h"

 #define ci(x) scanf("%d",&x)

 #define pi(x) printf("%d\n",x)

 using namespace std;

 int n,k;

 int work(int x){

     int cnt=;

     for(;x;x-=x&-x) cnt++;

     return cnt;

 }

 int main() {

     ci(n),ci(k);

     int ans=;

     while(work(n)>k) ans+=n&-n,n+=(n&-n);

     pi(ans);

 }

最新文章

1. Ubuntu下开启php调试模式，显示报错信息
2. ECshop后台角色权限的添加和分配
3. 【虚拟机】苹果虚拟机mac10.11.6+Xcode8.1
4. 基于docker＋etcd＋confd ＋ haproxy构建高可用、自发现的web服务
5. 使用dynamic类型改进反射
6. [iOS微博项目 - 3.2] - 发送微博
7. Find the Clones
8. php 操作数组 (合并,拆分,追加,查找,删除等)
9. hdu 4707 Pet（DFS水过）
10. Android生命周期注意事项
11. hdu--1800--字典树&&其他
12. MinGW是什么
13. 原生javascript学习
14. ORACLE 创建表空间、用户、授权
15. ABAP 开启制定路径下的文件或网址URL
16. pyecharts使用
17. python单元测试框架unittest总结
18. IDEL中easyui使用jstl和el出现传值不显示的问题
19. luasocket 安装记录 （FS1.6）
20. python 3 往Excel 中的写入内容但不覆盖原内容

热门文章

1. 软件测试技术第三次作业——打印质数printPrimes()
2. maven课程 项目管理利器-maven 3-5 maven生命周期和插件 4星
3. Python人工智能之初识接口
4. jQueryMobile（二）
5. memcached 的配置及 spymemcached 客户端简单使用
6. 搭建Web开发环境JavaEE_Eclipse
7. Homestead 安装 phpMyAdmin 作为数据库管理客户端 — Laravel 实战 iBrand API 教程
8. TP5.1：连接数据库（全局配置、动态配置、DSN配置）
9. 为什么CRM Opportunity的删除会触发一个通向BW系统的RFC
10. CPP-基础：类