（Java）P1223 排队接水

排队接水

一、 题目描述

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

二、输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的等待时间 $T_i$。

三、输出格式

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

四、样例输入

10 
56 12 1 99 1000 234 33 55 99 812
1
2

五、样例输出

3 2 7 8 1 4 9 6 10 5
291.90
1
2

六、代码

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

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)));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

七、注意点

①总等待时间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);
        }
1
2
3