杂题

Problem 1

有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$。

你可以任意排列这些人的站位，为最小的平均等待时间是多少？

数据范围：$N \leq 10^5$

要求答案 $\dfrac{S_1+S_2+\cdots+S_n}{n}$
最优方案 对于$T$数列, $T_1 \leq T_2\leq\cdots \leq T_n$
证明 $ T_1 \leq T_2 \leq T_3 \leq \cdots \leq T_n $ (方案$A$,贪心策略)，设在此策略下，有 $ T_1 \leq T_u \leq T_v \leq \cdots \leq T_n $
若 $u$ 和 $v$ 交换，则交换前和交换后 $u,v$ 总时间变为：$2u+v \to 2v+u$
$\because T_v \ge T_u, \therefore 2u+v$ 优于 $2v+u$，贪心策略成立，证毕。

Problem 2

原题请见【Luogu P1080 国王游戏】

每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。

要求答案 $\sum A_1\times A_2\times A_3\times \cdots\times A_i \div B_i$
最优方案 对于$A$中的$A_i$和$A_j(i\le j)$,满足$A_i\cdot B_i\leq A_j\cdot B_j$
证明 考虑相邻的$(A_1,B_1)$和$(A_2,B_2)$，若按原序为最优答案$\max{S\div B_1,S\times A_1/B_2}$
若调换它们的位置（得出的答案小于等于最优解）则为$\max{S\div B_2,S\times A_2/B_1}$
将上下相消则有$A_1\div B_2\leq A_2\div B_1$，十字相乘，证毕。