高精度好没前途,让python来拯救世界吧.
(参见y总的sol或蓝书)可知按a[i]*b[i]
升序是最优的方案,然后暴力模拟即可.但高精度让这题变得恶心了,于是利用python自带高精的特性.
两个注意点:
1. python的排序似乎不是很容易直接按a[i]*b[i]
升序,于是我再开一维存a[i]*b[i]
,然后直接list.sort()
就好.
2. python的/
会自动转成浮点数,用//
做到下取整.
以下是简短的代码:
n=int(input())
a,b=map(int,input().split())
prime=[(0,0,0)]
for i in range(1,n+1):
x,y=map(int,input().split())
prime.append((x*y,x,y))
prime.sort()
ans=0
mul=a
for i in range(1,n+1):
if(mul//prime[i][2]>ans):
ans=mul//prime[i][2]
mul*=prime[i][1]
print(ans)