acwing 913. 排队打水
有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
输入格式
第一行包含整数n。
第二行包含 n 个整数，其中第i个整数表示第i 个人装满水桶所花费的时间 ti。
输出格式
输出一个整数，表示最小的等待时间之和。
数据范围
输入样例：
7 3 6 1 4 2 5 7
输出样例：
56
思考过程/解题步骤:
这题考察的是一个贪心的思想，需要我们如何选取来达到最优的等待时间即最短的等待时间
下面给出这种贪心猜测的证明：
反证法：
这种思想可以额外引申到操作系统的进程调度算法：最短作业优先处理。这样子我们就可以很清楚的知道假设我们只想要得到最短等待时间之和这一项指标的话，那么我们就可以参照这里的思想去理解。同时，平时考试的时候为什么大部分人需要采取的策略是先易后难，跟这里的思想也许也有一定的关系，更少的空白等待思考时间。还有这里给了我一个启发，生活中如果遇到多件不能并发处理并且都不是很紧急但是又都很有必要做的事情，我以后就要根据时间长短优先处理能够先处理的，这样可以减少空白等待的时间。
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(String.valueOf(reader.readLine())); int[] arr = new int[n]; String[] num = reader.readLine().split(" "); for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(num[i]); } // 先排序 Arrays.sort(arr); long res = 0; for (int i = 0; i < n; i++) { // 第i名打水的后面会有n-i-1个等待的，因此等待的时间就是arr[i] * (n-i-1) res += (arr[i] * (n-i-1)); } writer.write(res + "\n"); writer.flush(); writer.close(); reader.close(); } }
