算法分析
- 安排他们的打水顺序才能使所有人的等待时间之和最小,则需要将打水时间最短的人先打水
证明:
不妨设
-
(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);
}
}
????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????????????????????????????????????????????????????
有bug哈哈哈哈
SJF
思路一模一样兄弟