洛谷 P1582 倒水

题目描述

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

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

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

输入输出格式

输入格式：

一行两个正整数， N,K( $10^9,Kle 10001≤N≤2×109,K≤1000)。$

输出格式：

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

输入输出样例

输入样例#1：

3 1

输出样例#1：

输入样例#2：

13 2

输出样例#2：

输入样例#3：

1000000 5

输出样例#3：

15808
解题思路:

首先明确一点，每个瓶中的水量都是2的幂，这个不难证明。其次，想要瓶子更少，则要尽可能把瓶子合并，这是什么意思呢？举个例子，输入N=13，K=2，先不考虑购买新瓶子和K，给出13个瓶子的两种合并方案，4 4 4 1和8 4 1。不废话，后者显然更好。其实也不难证明上面这条的最优性质，总之，我们总是希望尽可能把多的瓶子合并。实际算法不难，首先把瓶子先进行合并，最后总会得到一个无法再合并的结果，比如上面的8 4 1，但是这时候我们仍有三个瓶子，而数据要求我们最多剩下2个瓶子，所以我们第二步就是对最后两个瓶子进行合并，这时候直接4-1=3，即所求需要购买的瓶子数，于是最后两个瓶子可以合并为一个蓄水量为8的瓶子。

算法设计也比较简单，我这里用的是递归来实现。

func1(n,r): 返回将n个瓶子存入数组f之后，所使用的数组长度，r传入1。我们在这个函数中找到小于n的最大的2的幂y，这个数字填充数组当前位置，然后再递归调用func1(n-y,r+1)，返回其返回值。边界条件为n==0，此时直接返回r-1。

func2(n,r): 合并数组f中下标为r~n的瓶子，通常r<=n。两个边界条件：1.n<r+1，直接返回0，因为n绝对小于r，不需要合并。2.n==r+1，说明要合并的瓶子是相邻的两个，直接将他们合并，然后返回就好了。如果需要合并且合并的不是相邻两个瓶子，那么我们可以递归地调用func2(n,r+1)，这样会把编号为r+1到n的瓶子合并，于是我们就可以直接再把编号为r和r+1的瓶子合并，注意要计算结果。

AC代码:

 1 #include<cstdio>
 2 #define ll long long
 3 using namespace std;
 4 ll n,k,f[1005];
 5 int process1(ll n1,ll r) {
 6     if(!n1) return r - 1;
 7     ll y = 1;
 8     while(true) {
 9         if(y * 2 > n1) break;
10         y = y + y;
11     }
12     f[r] = y;
13     return process1(n1-y,r+1); 
14 }
15 int process2(ll n2,ll r) {
16     if(n2 < r + 1) return 0;
17     if(n2 == r + 1) {
18         ll y = f[r] - f[n2];
19         f[r] *= 2;
20         return y;
21     }
22     ll u = process2(n2,r+1);
23     ll e = f[r] - f[r+1];
24     f[r] *= 2; 
25     return u + e;
26 }
27 int main()
28 {
29     scanf("%lld%lld",&n,&k);
30     int t = process1(n,1);
31     int ans = process2(t,k);
32     printf("%d",ans);
33     return 0;
34 }