蓝桥杯备考:模拟+堆 ---接水问题
这道题的思路就是,一共有m个水龙头,n个同学,我们要求接水总时间,我们只要用堆来模拟水龙头接水就行了,最开始所有水龙头初始都是0秒
初始化完之后,我们每次都取出小根堆的堆顶,输入一个数加到堆顶上,每次都取最小的来负责切换人,最后这三个水龙头时间最长的就是我们的答案
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m;
int main()
{
cin >> n >> m;
priority_queue<int,vector<int>,greater<int>> heap;
for(int i = 1;i<=m;i++)
{
heap.push(0);
}//最开始m个水龙头都是0秒,
int ret = 0;
for(int i =1;i<=n;i++)
{
int x;cin >> x;
int t = heap.top();heap.pop();
t+=x;
heap.push(t);
}
while(heap.size())
{
int t = heap.top();heap.pop();
ret = max(ret,t);
}
cout << ret << endl;
}