排队接水问题(C++、贪心)

学校算法与设计课上的一个讨论题，一个比较经典的贪心问题

题目描述(大概是这个意思吧，如果有误请大家务必指正)
现在有n个人排队去r个水龙头口打水，他们接满水的时间分别是t1,t2,t3…tn(都是整数)，怎样安排他们打水的顺序才能让他们花费的总时间最少？

输入1:

4 2
2 4 5 6

输出1:

23

输入2:

7 3
2 3 1 6 9 4 5

输出2:

41

思路：按打水时间从小到大的顺序将所有人排序，接着确定好每个接水口前的队伍的排列顺序，也就是找出每个人应该排在哪个接水口和排在第几位(题目稍微复杂的地方就在这里)，然后分别计算出每个队伍的用时，将所有队伍的用时累加起来就可以得到题目中所要求出的总的用时了，具体代码和详细注释如下(肯定有更好的解决思路，但我只能想出来这个 ╮(╯﹏╰）╭)

#include
using namespace std;
priority_queue<int, vector<int>, greater<int>> q; //定义优先队列(小顶堆，元素从小到大排列)
int main() {int n, r, t;                    //其中n为接水人数，r为接水口的数量cin >> n >> r;for (int i = 0; i < n; i++) {cin >> t;                   //输入当前这个人的接水时间q.emplace(t);               //将接水时间存入优先队列}vector<int> v[100];             //使用二维vector数组存放在每个接水口排队的人int flag = 0, k = 0;            //flag用于判断当前是否应该从第一队重新插入for (int i = 0; i < n; i++) {if (flag == r) {            //当flag值等于接水口数量值的时候，当前的人需要从第一队重新插入flag = 0;               //flag归0k = 0;                  //队伍重新回到第一队,因为第一队的vector下标实际为0,所以让k也归0}v[k].emplace_back(q.top()); //按顺序将优先级队列中等待的人插入他应该排的那个队伍q.pop();                    //插入之后让当前的人出队flag++;                     //flag值加1k++;                        //队伍的序号加1}int sum_water = 0;              //sum_water为所有队伍中所有人的等待时间与打水时间之和,即总时间for (int i = 0; i < r; i++) {   //遍历每个队列int sum_wait = 0;           //sum_wait临时储存当前队列中所有人花费的时间for (auto x : v[i]) {sum_wait += x;sum_water += sum_wait;  //在循环中将时间累加，和算前缀和很像}}cout << sum_water;              //输出结果return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！