[noip2012]国王游戏

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

$$maxleft { frac{pre}{R_{i}} frac{pre*L_{i}}{R_{i+1}} right }$$

交换之后则为

$$maxleft { frac{pre}{R_{i+1}} , frac{pre*L_{i+1}}{R_{i}} right }$$

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

$$maxleft { frac{1}{R_{i}} , frac{L_{i}}{R_{i+1}} right }quad quad quad maxleft { frac{1}{R_{i+1}},frac{L_{i+1}}{R_{i}} right }$$

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

$$maxleft { R_{i+1} , L_{i}R_{i} right }quad quad quad maxleft { 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

1
2
3
4
5
6
7
8
9
10
11
12
13

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="")