东华OJ-进阶题-19-排队打水问题（C++）

• 问题描述
  有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2…………tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
• 输入说明
  第一行n，r (n<=500,r<=75)
  第二行为n个人打水所用的时间Ti (Ti<=100)；
• 输出说明
  最少的花费时间
• 输入范例

32123

• 输出范例

7

感想：用到priority_queue SJF最短作业优先策略就方便很多，pq 堆排序适合贪心。
代码如下：

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,r;cin>>n>>r;vector<int>cost(n);for(inti=0;i<n;++i){cin>>cost[i];}sort(cost.begin(),cost.end());// 小顶堆，存储每个水龙头的当前累计时间priority_queue<int,vector<int>,greater<int>>pq;for(inti=0;i<r;++i){pq.push(0);// 初始所有水龙头空闲}inttotal=0;// 总花费时间for(inti=0;i<n;++i){intcurr=pq.top();pq.pop();total+=curr+cost[i];pq.push(curr+cost[i]);//更新水龙头目前时间}cout<<total<<endl;return0;}