洛谷P1582 倒水
题目描述
一天,CC买了N个容量可以认为是无限大的瓶子,开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了,于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子,把一个瓶子的水全部倒进另一个里,然后把空瓶丢弃。(不能丢弃有水的瓶子)
显然在某些情况下CC无法达到目标,比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限,开始时有1升水),以到达目标。
现在CC想知道,最少需要买多少新瓶子才能达到目标呢?
题目解析
这道题看了很多大佬都是用位运算来完成的,但是我是借用优先队列来模拟这个过程,也成功AC了。接下来讲一下思路。
加入现在有9个瓶子,当前含水量都是1。
第一次合并含水量相同的瓶子,由9个1可以变成4个2和1个1。第二次继续合并含水量相同的瓶子,由4个2和1个1变成2个4和1个1。第三次继续合并后变成1个8和1个1。由于当前已经没有含水量相同的瓶子了,所以第一步操作结束。
将8和1压入优先队列(小根堆)判断现在堆元素个数是否大于k,如果大于k,就推出最小元素,结果result加上当前最小元素,然后将当前元素*2再压入优先队列,重复这个循环直至堆元素个数等于k。
代码实现
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int n,k,o=1,ans;
int main(){
cin >> n >> k;
priority_queue<int, vector<int> , greater<int> > q;
while(n > 0){
if(n % 2 == 1){
q.push(o);
}
o*=2;
n/=2;
}
while(q.size() > k){
int a = q.top();
q.pop();
int b = q.top();
q.pop();
if(a == b){
q.push(a+b);
}else{
q.push(b);
ans+= a;
q.push(a*2);
}
}
cout << ans << endl;
}