算法分析

• 安排他们的打水顺序才能使所有人的等待时间之和最小，则需要将打水时间最短的人先打水

证明：

不妨设

• (1)$i_1$ ≠ $i_2$ ≠ $i_3$ ≠ … ≠ $i_n$

• (2)$i_1$~$i_n$属于$[1,n]$

• (3)$t_1$ < $t_2$ < $t_3$ <… < $t_n$,

1、由i的任意性，打水的时间总和为$t_{i_1}$ * (n - 1) + $t_{i_2}$ * (n - 2) + … + $t_{i_n}$ * (n - n)
=n * ($t_{i_1}$ + $t_{i_2}$ +… + $t_{i_n}$) - ($t_{i_1}$ * 1 + $t_{i_2}$ * 2 + … + $t_{i_n}$ * n)

2、即相当于求 $t_{i_1}$ * 1 + $t_{i_2}$ * 2 + … + $t_{i_n}$ * n 的最大值

3、假设$t_{i_1}$ , $t_{i_2}$ ,… , $t_{i_n}$是按自然顺序排好序时是最大值，即$T_{max}$ = $t_1$ * 1 + $t_2$ * 2 + … + $t_n$

4、任意选择两项$t_a * x$,$t_b * (x + c)$,且$t_a$ < $t_b$,c > 0,交换$t_a$,$t_b$位置得到$t_b * x$,$t_a * (x + c)$ ,同时交换后不会对其他项造成影响
由于$t_a$ * x + $t_b$ * (x + c) = $t_a$ * x + $t_b$ * x + $t_b$ * c > $t_a$ * x + $t_b$ * x + $t_a$ * c = $t_b$ * x + $t_a$ * (x + c),即交换之后比原来的值更小.由于选取的任意性可得假设成立.

时间复杂度 $O(nlogn)$

Java 代码

import java.util.*;


public class Main{

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int[] a = new int[n + 1];
        for(int i = 1;i <= n;i++)
        {
            a[i] = scan.nextInt();
        }
        Arrays.sort(a);
        long res = 0;
        for(int i = 1;i <= n;i++)
        {
            res += (a[i] * (n - i));
        }
        System.out.println(res);

    }

}