Dark`Kris

Private blog

I'm spark , hope you fire


Luogu P1582 倒水 解题报告

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

题目描述

一天,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×10 9 ,K≤1000 )。

输出格式:

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

输入输出样例

输入样例#1: 3 1 输出样例#1: 1

输入样例#2: 13 2 输出样例#2: 3

输入样例#3: 1000000 5 输出样例#3: 15808


解题思路

这是一个很巧妙的数学题

这道题显然和二进制是有关系的

合并前 二进制 合并后
1 1 1
2 10 1
3 11 2
4 100 1
5 101 2
6 110 2
7 111 3

显然有:合并后 = 合并前二进制中1的个数

那么怎么求1的个数呢?

在树状数组的使用中我们会使用到一个函数low(x),函数的内容是

int low(int x)
{
	return x&-x;
}

而这个函数的作用就是把x的最低位1的数表示出来(如下表)

x x(2) low(x) low(x)(2)
1 1 1 1
2 10 2 10
3 11 1 1
4 100 4 100
5 101 1 1
6 110 2 10

所以我们用一下代码即可求出1的个数

int getone(int x)
{
    int ret=0;
    while(x)
    {
        x-=(x&-x);
        ret++;
    }
    return ret;
}

再稍加优化,即可得出答案:

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,k,ans;
int getone(int x)
{
    int ret=0;
    while(x)
    {
        x-=(x&-x);
        ret++;
    }
    return ret;
}
int main()
{
    scanf("%d %d",&n,&k);
    while(getone(n)>k)
    {
        ans+=(n&-n);
        n+=(n&-n);
    }
    printf("%d",ans);
    return 0;
}

感谢阅读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading