Luogu

分析

假设不交换 $i$ 和 $i+1$ 更优,那么有

$$ \max\left\{\frac{s_{i-1}}{b_i},\frac{s_{i-1}a_i}{b_{i+1}}\right\}<\max\left\{\frac{s_{i-1}}{b_{i+1}},\frac{s_{i-1}a_{i+1}}{b_i}\right\} $$

显然有

$$ \begin{aligned} \frac{s_{i-1}}{b_i}&\leq\frac{s_{i-1}a_{i+1}}{b_i}\\ \frac{s_{i-1}}{b_{i+1}}&\leq\frac{s_{i-1}a_i}{b_{i+1}} \end{aligned} $$

因此上式化为

$$ \frac{s_{i-1}a_i}{b_{i+1}}<\frac{s_{i-1}a_{i+1}}{b_i} $$

进一步得到

$$ a_ib_i<a_{i+1}b_{i+1} $$

因此只要按 $a_i\times b_i$ 排个序,然后写个高精度就好了。

代码

蒯来的 py3 代码

n = int(input())
tmp = input().split();
a = int(tmp[0])
b = int(tmp[1])
o = []
for i in range(0,n):
    tmp = input().split()
    o.append((int(tmp[0]),int(tmp[1])))
o.sort(key=lambda x:x[0]*x[1])
ans = 0
for i in range(0,n):
    if a // (o[i])[1] > ans:
        ans = a // (o[i])[1]
    a = a * (o[i])[0]
print(ans)
最后修改:2019 年 10 月 25 日 11 : 48 AM