洛谷P1582 倒水

「爱情、让人受尽委屈。」 2022-05-25 02:30 144阅读 0赞

## 题目描述 ##

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

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

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

## 输入输出格式 ##

输入格式：

一行两个正整数， N,K( 1\\le N\\le 2\\times 10^9,K\\le 10001≤*N*≤2×109,*K*≤1000 )。

输出格式：

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

## 输入输出样例 ##

输入样例\#1： 复制

3 1

输出样例\#1： 复制

1

输入样例\#2： 复制

13 2

输出样例\#2： 复制

3

输入样例\#3： 复制

1000000 5

输出样例\#3： 复制

15808

位运算：

参考:[https://www.luogu.org/blog/user36297/solution-p1582][https_www.luogu.org_blog_user36297_solution-p1582] 讲的很详细

i&-i

这个式子返回的值就是从后往前数，到第一个1出现为止的数(二进制下)。

来列个表：

<table style="border-spacing:0px;max-width:100%;color:rgb(51,51,51);font-family:'Segoe UI', 'Lucida Grande', Helvetica, Arial, 'Microsoft YaHei', FreeSans, Arimo, 'Droid Sans', 'wenquanyi micro hei', 'Hiragino Sans GB', 'Hiragino Sans GB W3', FontAwesome, sans-serif;font-size:15px;line-height:24px;"> 
 <thead> 
  <tr> 
   <th style="padding:0px;">i</th> 
   <th style="padding:0px;text-align:right;">i(2)</th> 
   <th style="padding:0px;">i&amp;-i</th> 
   <th style="padding:0px;text-align:right;">i&amp;-i(2)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:6px 13px;">1</td> 
   <td style="padding:6px 13px;text-align:right;">1</td> 
   <td style="padding:6px 13px;">1</td> 
   <td style="padding:6px 13px;text-align:right;">1</td> 
  </tr> 
  <tr> 
   <td style="padding:6px 13px;">2</td> 
   <td style="padding:6px 13px;text-align:right;">10</td> 
   <td style="padding:6px 13px;">2</td> 
   <td style="padding:6px 13px;text-align:right;">10</td> 
  </tr> 
  <tr> 
   <td style="padding:6px 13px;">3</td> 
   <td style="padding:6px 13px;text-align:right;">11</td> 
   <td style="padding:6px 13px;">1</td> 
   <td style="padding:6px 13px;text-align:right;">1</td> 
  </tr> 
  <tr> 
   <td style="padding:6px 13px;">4</td> 
   <td style="padding:6px 13px;text-align:right;">100</td> 
   <td style="padding:6px 13px;">4</td> 
   <td style="padding:6px 13px;text-align:right;">100</td> 
  </tr> 
  <tr> 
   <td style="padding:6px 13px;">5</td> 
   <td style="padding:6px 13px;text-align:right;">101</td> 
   <td style="padding:6px 13px;">1</td> 
   <td style="padding:6px 13px;text-align:right;">1</td> 
  </tr> 
  <tr> 
   <td style="padding:6px 13px;">6</td> 
   <td style="padding:6px 13px;text-align:right;">110</td> 
   <td style="padding:6px 13px;">2</td> 
   <td style="padding:6px 13px;text-align:right;">10</td> 
  </tr> 
  <tr> 
   <td style="padding:6px 13px;">7</td> 
   <td style="padding:6px 13px;text-align:right;">111</td> 
   <td style="padding:6px 13px;">1</td> 
   <td style="padding:6px 13px;text-align:right;">1</td> 
  </tr> 
  <tr> 
   <td style="padding:6px 13px;">8</td> 
   <td style="padding:6px 13px;text-align:right;">1000</td> 
   <td style="padding:6px 13px;">8</td> 
   <td style="padding:6px 13px;text-align:right;">1000<br></td> 
  </tr> 
 </tbody> 
</table>

#include<iostream>
    using namespace std;
    
    int get(int n)
    {
    	int num = 0;
    	for (;n;n-=n&-n)
    	{
    		num++;
    	}
    	return num;
    }
    
    int n, k , ans;
    int main()
    {
    	cin >> n >> k;
    	while (get(n) > k)
    	{
    		ans += n&-n;
    		n += n&-n;
    	}
    	cout << ans;
    	return 0;
    }

[https_www.luogu.org_blog_user36297_solution-p1582]: https://www.luogu.org/blog/user36297/solution-p1582

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷P1223 排队接水

我不知道为什么我最近喜欢JAVA了…… 韩顺平老师的课真好听呀贪心本章节：排队接水题目描述有 nn 个人在一个水龙头前排队接水，假如每个人接水

淡淡的烟草味﹌/ 2023年07月10日 08:20/ 0 赞/ 2 阅读

相关 P1582-倒水

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

太过爱你忘了你带给我的痛/ 2023年06月01日 08:52/ 0 赞/ 11 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 322 阅读

相关洛谷P1582 倒水

题目描述一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相

「爱情、让人受尽委屈。」/ 2022年05月25日 02:30/ 0 赞/ 145 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 317 阅读

相关洛谷P1540——机器翻译

题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

傷城~/ 2022年04月14日 06:55/ 0 赞/ 304 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 350 阅读

相关洛谷p1208 水题贪心思想入门

题目描述由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。 Marry乳业从一些奶农手中采购牛奶，并且每一位

今天药忘吃喽~/ 2021年12月24日 08:07/ 0 赞/ 367 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 439 阅读

相关 P1582 倒水

太强了，dalao的题解 [https://www.luogu.org/blog/jingyangzhi/solution-p1582][https_www.luogu.or

秒速五厘米/ 2021年10月26日 12:32/ 0 赞/ 375 阅读