[NOIP2012]国王游戏

考虑第i 个和第i+1 个位置

$$max\left \{ \frac{pre}{R_{i}} \frac{pre*L_{i}}{R_{i+1}} \right \}$$

交换之后则为

$$max\left \{ \frac{pre}{R_{i+1}} , \frac{pre*L_{i+1}}{R_{i}} \right \}$$

其他人的并没有改变
提取pre

$$max\left \{ \frac{1}{R_{i}} , \frac{L_{i}}{R_{i+1}} \right \}\quad \quad \quad max\left \{ \frac{1}{R_{i+1}},\frac{L_{i+1}}{R_{i}} \right \}$$

同乘$R_{i}*R_{i+1}$

$$max\left \{ R_{i+1} , L_{i}R_{i} \right \}\quad \quad \quad max\left \{ R_{i}, L_{i+1}R_{i+1} \right \}$$

L,R 均为正整数

$$R_{i}< L_{i}R_{i} \quad \quad \quad R_{i+1}< L_{i+1}R_{i+1}$$ $$L_{i}R_{i} \quad \quad \quad L_{i+1}R_{i+1}$$

因此将$L*R$较小的放在前面更优

人生苦短，我用Python

n = int(input())
x, y = map(int, input().split())
w = []
for i in range(0, n):
    L, R = map(int, input().split())
    w.append({"L": L, "R": R, "val": L * R})
w.sort(key=lambda node: node["val"])
cnt = x
ans = 0
for i in range(0, n):
    ans = max(ans, cnt // w[i]["R"])
    cnt *= w[i]["L"]
print("%d" % ans, end="")