[NOIp2012] 国王游戏（排序 + 贪心 + 高精度） 题意 题解 总结 代码
给你两个长为 (n+1) 的数组 (a,b) ，你需要定义一个顺序 (p) （(p_0) 永远为 (0)）
能够最小化
[max_{i=1}^{n} frac{prod_{j = 0}^{i} a_{p_j}}{b_{p_i}}
]
(1 le n le 1000, 1 le a, b le 10^4)
题解
开始把原来没做完的 (NOIp) 题都水掉qwq
类似这种题都需要有个巧妙的排序方法，使得答案最小，其实可以大力找规律或者猜结论发现按 (a_i imes b_i) 排序是最优秀的。
我们尝试推导这个结论。
其实我们发现只需要考虑相邻两个数如何交换才是最优的，因为任意排列都可以由交换相邻两个数得到。
假设当前两个位置为 (i, i+1) ，记 (displaystyle p = prod_{j = 0}^{i - 1}a_j) 。
我们令 (ans_0) 为交换前的最大值，(ans_1) 为交换后的，那么有
[egin{cases}
ans_0 &= max{frac{p}{b_i}, frac{p imes a_i}{b_{i+1}}} \
ans_1 &= max{frac{p}{b_{i+1}}, frac{p imes a_{i+1}}{b_{i}}}
end{cases}
]
因为有
[forall i, a_i, b_i ge 1
]
不难发现有
[egin{cases}
displaystyle frac{p imes a_i}{b_{i+1}} ge frac{p}{b_{i+1}} \
displaystyle frac{p imes a_{i+1}}{b_{i}} ge frac{p}{b_i}
end{cases}
]
所以当 (ans_1 ge ans_0) 也就是交换后不会更优，当且仅当
[egin{aligned}
frac{p imes a_{i+1}}{b_{i}} &ge frac{p imes a_i}{b_{i+1}} \
a_{i + 1} imes b_{i + 1} &ge a_i imes b_i
end{aligned}
]
所以我们不难发现当 (a_i imes b_i) 升序的时候是最优的。
然后答案需要用高精度存储，但是我不想写。。。（用 (python) 水过了2333）
考试时候应该还是会头铁写高精度的。。
总结
对于重排序列使得一些要求的东西最优的时候，可以考虑不等式推导。
然后也不需要考虑相隔很远的两个数，可以考虑相邻两个数，结论也是一样的，因为交换相邻两个数也可以使得序列排序。
代码
教你 (17) 行 (python3) 代码水过2333
n = (int)(input())
a, b = map(int, input().split())
array = [[0] * 2] * n
for i in range(0, n):
array[i] = list(map(int, input().split()))
def Cmp(elem):
return elem[0] * elem[1]
array.sort(key = Cmp)
ans = 0
tot = a
for i in range(0, n):
ans = max(ans, tot // array[i][1])
tot = tot * array[i][0]
print(ans)