蓝桥杯 ADV-148 排队打水问题

打水问题"/>

蓝桥杯 ADV-148 排队打水问题

蓝桥杯 ADV-148 排队打水问题

问题描述

有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2…………tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？

输入格式
第一行n，r (n<=500,r<=75)
第二行为n个人打水所用的时间Ti (Ti<=100)；
输出格式
最少的花费时间
样例输入
3 2
1 2 3

样例输出
7

思路解析

使用贪心策略：即优先让耗时少的人先打水。

为什么使用这种策略可以得到最优解呢？

打水的情况无非两种，一种是耗时长的人先打水，一种是耗时短的人先打水。

我们知道，每个人打水花费的总时间S=装水时间T+等待时间W

不管是哪一种情况，每个人打水的装水时间是不会变的，情况的不同只影响等待时间的长短，很容易可以看出，装水时间短的人优先打水，则后续打水的人的等待时间较装水时间长的人优先打水 更短。

所以，我们采用这样的策略：优先让装水时间短的人先打水。

在程序中，我们使用 t t t 来记录每个人的装水时间，而让 w w w 记录每个人的等待时间，而每个人的等待时间取决于他所在水龙头中之前所有人的装水时间，依据这样的关系，我们可以得到求解的程序。如下：

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;int main()
{int n, r, sum = 0;cin >> n >> r;vector<int> t(n), w(r);for (int i = 0; i < n; i++){cin >> t[i];}sort(t.begin(), t.end());// 第一批接水for (int i = 0; i < r; i++){sum += t[i];w[i] = t[i];}// 后续批次接水for (int i = r; i < n; i++){int index = (i + 1) / r - 1; // 索引循环sum += t[r] + w[index];w[index] += t[i];}cout << sum;return 0;
}