P1582 倒水 题解
2024-08-28 14:16:58
来水一发水题。。
题目链接。
正解开始:
首先,我们根据题意,可以得知这是一个有关二进制的题目;
具体什么关系,怎么做,我们来具体分析:
对于每个n,我们尝试将其二进制分解,也就是100101之类的形式
根据瓶子合并的特性,我们可以判定最后每一个瓶子内的水都可以表示成2^i的形式
感性理解:对于每一个数位上为1的地方,自然,他可以经过多次合并(瓶子加水)来合成,因为每个瓶子内的水都可以表示成2^i的形式,也就对应着n二进制分解上的一个1.
说白了就是从开始的那一堆瓶子里面进行合成,最后在不加瓶子的情况下,必定会合成为n的二进制分解的形式,其中1的个数为瓶子剩余的个数。
那么我们求n的二进制分解中有多少个1,如果1的个数比k小了,说明经过一系列令人窒息的操作后我们在不加瓶子的情况下能够最后剩余的瓶子个数。如果比k要大的话,我们考虑加瓶子:
举个例子:18 用二进制表示的话就是:1010
其中剩余两个瓶子,其中内的水量分别是16L,2L。如果我们要求k=1,也就是只剩下1个瓶子的话,那么我们贪心的考虑,自然买的瓶子量越少越好,也就是从二进制位右边开始,检测1,这时检测到了内含有2L水的瓶子,要想合并,自然要另外找新瓶子并合并成和当前瓶子容量一致的新瓶子,也就是我们还需要1个2L水的瓶子,那么自然的,我们需要两瓶新水,把2累加到答案ans上。
10010+10=10100;
10100+100=11000;
11000+1000=100000;
这时候只剩下1瓶内含有32升水的瓶子。符合k=1的要求
那么答案就是10+100+1000=1110(二进制)=14升水=14个新瓶子。
思路讲解完毕,代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int read()
{
int ans=;
char ch=getchar(),last=' ';
while(ch<''||ch>'')last=ch,ch=getchar();
while(ch>=''&&ch<='')ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
return last=='-'?-ans:ans;
}
int n,k,ans;
int lowbit(int x)
{
return x&(-x);
}
int find1(int n)
{
int num=;
while(n>)
{
num+=(n&==?:);
n>>=;
}
return num;
}
int main()
{
n=read();k=read();
while(find1(n)>k)
{
ans+=lowbit(n);n+=lowbit(n);
}
printf("%d",ans);
}
完结
最新文章
- windows下用QTwebkit解析html
- SQL键值约束、索引使用
- Oracle数据库3
- [leetcode] Rectangle Area
- C#Form窗体通过代码改变尺寸
- NOI 2004 郁闷的出纳员(平衡树)
- linux使用flock文件锁解决crontab冲突问题
- core--线程状态
- Android的ListView分页功能
- RTMP
- SharedPreferences数据、openFileOutput文件、SQLite数据库文件存储位置
- 隐私模式启动IE 谷歌浏览器
- HTML5表单增强
- Android学习之 AChartEngine 图表绘制
- chap1 C++泛型技术基础--模板 #STL
- webpack入门教程--1
- python 进程锁 生产者消费者模型 队列 (进程其他方法,守护进程,数据共享,进程隔离验证)
- 一个不错的Node.js进阶学习引导
- mkdir 获得新建文件权限
- 【BZOJ4774】修路(动态规划,斯坦纳树)