本蒟蒻第二篇题解 希望支持 优先队列做法

                                  此题解为优先队列做法

首先观察不难发现 这个接水顺序肯定是按照个人的接水时间升序去排列的.
因为 如果你先让时间最长的人去接,后面的每个人需要的等待时间也会加上他的时间,明显会更长.
反之 如果你让时间最短的人先做,后面的每个人要的时间加的就会相对少一点.
举个简单的例子
输入样例:
2 1
1 1000

如果是个正常人 是你 肯定会让1的人先做 这样总耗时就是1+(1000+1)=1002.
如果让1000的人先做 总耗时就变成了1000+(1000+1)=2001. 明显不符合要求

那么明白了思路 我们就知道可以让数组进行排序,从而达到升序的目的
但是
如果每一次计算都要排序 时间太容易乐
这时请出这篇题解的主角主要部分--------优先队列

如果不会请点击 传送门 这里不做过多讲解

直接奉上AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x;
queue <int> q;
priority_queue<int ,vector<int>,greater<int> >pq;//升序优先队列
int main(){
	cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x;
        q.push(x);
        if(pq.size() < min(n,m)){
            q.pop();
            pq.push(x);
        }
    }
    //等候接水
	while(!q.empty()){
        int t=pq.top();
        pq.pop();
        pq.push(q.front()+t);
        q.pop();
    }
    //求pq最大值
    int maxn=0;
    while(!pq.empty()){
        maxn=max(maxn,pq.top());
        pq.pop();
    }
    cout<<maxn;
	return 0;
}