Algorithm - Problem - 倒水

倒水 洛谷 P1582

问题描述

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

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

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

输入

一行两个正整数, N,K(1N2×109,K1000N,K(1\leqslant N\leqslant 2\times 10^9 ,K\leqslant 1000)。

输出

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

样例输入1
1
3 1
样例输出1
1
1
样例输入2
1
13 2
样例输出2
1
3
样例输入3
1
1000000 5
样例输出3
1
15808

二进制相关

分析

考虑到每一轮合并必然是成对成对的合并,不难发现将 NN 写为二进制后,有多少个 11,那么最终就剩下多少个瓶子.
假设剩余 RR 个瓶子,RKR\leqslant K 时,不需要购买新瓶子.
重点在于需要购买新瓶子的情况,新买 11 个瓶子相当于原先的 NN 变成 N+1N + 1,问题转化为求出满足条件的最小 NN'.
首先有 N>NN' > N,为了使其满足条件,至少要消除 RKR - K 个剩余的瓶子,也就是说在原先的 NN 的二进制种,至少要让 RKR - K11 消失不见.
但是在消除的过程中,一定会产生进位,因此我们通过不断加 11 的方式,实际要消除的个数应该是 RKR - K11.
接下来是让 NN' 最小,消除右侧的 11 才能使加的次数最少.
需要注意的是,连续的 11 进位后会产生连锁,因此需要找到右侧第 RK+1R - K + 111 的左侧第一个 00 的位置,进行位运算即可.
Water
计算出 NN' 后,与原 NN 作差即得答案.

话说我看了一下洛谷题解,发现神犇们的方法都太神奇了,根本比不上.

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

int main()
{
long long NO, N, K, P = 0, R = 0, T = 0;
std::cin >> NO >> K;
N = NO;
while(N != 0)
{
if(N & 1)
{
R++;
}
N = N >> 1;
}
if(R > K)
{
P = 0;
N = NO;
while(T <= R - K && N != 0)
{
if(N & 1) T++;
N = N >> 1;
P++;
}
while(N & 1)
{
N = N >> 1;
P++;
}
N = ((NO >> (P)) | 1LL) << (P);
std::cout << N - NO;
}
else
{
std::cout << 0;
}
}