排队接水

一、 题目描述

有 nnn 个人在一个水龙头前排队接水，假如每个人接水的时间为 TiT_iTi​，请编程找出这 nnn 个人排队的一种顺序，使得 nnn 个人的平均等待时间最小。

二、输入格式

第一行为一个整数 nnn。

第二行 nnn 个整数，第 iii 个整数 TiT_iTi​ 表示第 iii 个人的等待时间 TiT_iTi​。

三、输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

四、样例输入

10 
56 12 1 99 1000 234 33 55 99 812

五、样例输出

3 2 7 8 1 4 9 6 10 5
291.90

六、代码

具体代码如下啦，整体还是很简单的~
要让平均排队时间最小，就要让打水快的人往前排

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int i, j, temp1, temp2;double result = 0;int t[] = new int[10000];int l[] = new int[10000];for (i = 0; i < n; i++) {t[i] = sc.nextInt();l[i] = i + 1;}for (i = 0; i < n; i++) {for (j = i + 1; j < n; j++) {if (t[i] > t[j]) {temp1 = t[i];t[i] = t[j];t[j] = temp1;temp2 = l[i];l[i] = l[j];l[j] = temp2;}}}for (i = 0; i < n; i++) {result += t[i] * (n - i - 1);}for (i = 0; i < n; i++) {System.out.print(l[i] + " ");}System.out.println();System.out.println(String.format("%.2f", (result / n)));}
}

七、注意点

①总等待时间result应该设为double型

一开始我将result的值设为了float型，输入样例时结果是正确的，但提交后发现还是有部分答案是错误的，红红一片，太可怕了，经过尝试，发现是精度出现了问题。

②如何计算总等待时间result

• 注意，总等待时间并不是单单把每个人接水的时间加起来就可以了，而是要将每个人等待的时间都算入。
• 我们可以找一下规律
• 我们可以发现n个人等待，假设第3个人打水的时间为t[2]，则排在第三个人之后的所有人的等待时间都要加上t[3]，即总等待时间要加上（n-3）* t[2]，从第一个人开始依次遍历累加即可。
• 换成普遍规律就是

        for (i = 0; i < n; i++) {result += t[i] * (n - i - 1);}