题解 P1080 【国王游戏】

llbbyy · 2020-02-09 22:40:02 · 题解

看到前面好多题解都要分析，排序，我（？？？）。 这个题个人感觉完全不需要排序啊，首先把所有人的左手的值全部乘起来，之后遍历一次除开国王之外的人，尝试用总的值除以这个人的左手右手的值，取这个过程中最小的值就可以了，因为无论怎么排，获得最大钱数的人一定是最后那个人，钱数一定是前面所有人左手值的乘积除以自己的右手值，也就是所有人的的左手值的成绩除以自己的左右手值，这样遍历一下只需要O(n)就可以解决问题了

n=int(input())
sum=1
arr=[]
for i in range(n+1):
    in_put=input().split()
    sum*=int(in_put[0])
    arr.append(int(in_put[0]))
    arr.append(int(in_put[1]))
min=sum
for i in range(1,n+1):
    if sum//arr[i*2]//arr[i*2+1]<min:
        min=sum//arr[i*2]//arr[i*2+1]
if min==0:
    min=1
print(min)