1 / 15 贪心法习题汇总排队接水源程序名.???（, , ）可执行文件名输入文件名输出文件名【问题描述】有个人在一个水龙头前排队接水，假如每个人接水的时间为，请编程找出这个人排队的一种顺序，使得个人的平均等待时间最小。【输入】输入文件共两行，第一行为；第二行分别表示第个人到第个人每人的接水时间，，⋯，，每个数据之间有个空格。【输出】输出文件有两行，第一行为一种排队顺序，即到的一种排列；第二行为这种排列方案下的平均等待时间( 输出结果精确到小数点后两位) 。【样例】【算法分析】平均等待时间是每个人的等待时间之和再除以，因为是一个常数， 所以等待时间之和最小，也就是平均等待时间最小。假设是按照的自然顺序排列的，则这个问题就是求以下公式的最小值：niijjnTTTTTTTTTTtotal1121321211)()()(如果用穷举的方法求解，就需要我们产生个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行!次求和以及判断，时间复杂度很差！其实，我们仔细研究一下上面的公式，发现可以改写成如下形式：niinnTinTTTnTnnTtotal11321)1(2)2()1(这个公式何时取最小值呢？对于任意一种排列, , , ⋯, ，当1kT≤2kT≤3kT≤⋯≤nkT时，取到最小值。如何证明呢？方法如下：因为njikkkkkTTjnTinTnnTtotal)1()1()1(21假设 <，而ikT
