洛谷 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×109,K≤1000)。
输出格式:
一个非负整数,表示最少需要买多少新瓶子。
输入输出样例
3 1
1
13 2
3
1000000 5
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代码:
#include<cstdio>
#define ll long long
using namespace std;
ll n,k,f[];
int process1(ll n1,ll r) {
if(!n1) return r - ;
ll y = ;
while(true) {
if(y * > n1) break;
y = y + y;
}
f[r] = y;
return process1(n1-y,r+);
}
int process2(ll n2,ll r) {
if(n2 < r + ) return ;
if(n2 == r + ) {
ll y = f[r] - f[n2];
f[r] *= ;
return y;
}
ll u = process2(n2,r+);
ll e = f[r] - f[r+];
f[r] *= ;
return u + e;
}
int main()
{
scanf("%lld%lld",&n,&k);
int t = process1(n,);
int ans = process2(t,k);
printf("%d",ans);
return ;
}
最新文章
- java中异常注意的细节2
- sql server 2008 不允许保存更改,您所做的更改要求删除并重新创建以下表 的解决办法
- IP 协议首部格式与其配套使用的四个协议(ARP,RARP,ICMP,IGMP)
- 【JAVA、C++】LeetCode 005 Longest Palindromic Substring
- winston 日志管理4
- (七)DAC0832 数模转换芯片的应用 以及运算放大器的学习 01
- C#重启系统代码
- socket编程(Linux)
- HDU 1465 不容易系列之一(错排,递归)
- Uubuntu 14.04 LTS反编译apk
- Disabling Clang Compiler warnings
- HTML&;CSS基础学习笔记1.5-添加常用标签
- C# 内存泄露
- stack 集合栈计算机 (摘)
- web前端好学吗?
- Java数据结构和算法(十三)——哈希表
- 《重构》中Tips总结
- redis 系列7 数据结构之跳跃表
- php json_encode中提示的中文总是返回";\u767b\u5f55\u6210\u529f\uff01";的解决办法
- 爬虫基础以及 re,BeatifulSoup,requests模块使用