blablabla
算法1
(暴力枚举) $O(n^2)$
时间复杂度为$O(n^2)$,由于最大为$10^9$,因此肯定是过不了的。在蓝桥官方OJ只过了30%(用C++枚举几乎可以过100%,可能因为python运行速度较慢)
python代码(只过了30%)
import os
import sys
n=int(input())
a=[]
for _ in range(n):
x,y=map(int,input().split())
a.append((x,y))
min_idx,max_idx=1000000,1
for k in range(1, 1000000):
ok = True
for i in range(n):
if a[i][0]//k !=a[i][1]:
ok=False
continue
if ok:
min_idx=k
break
for k in range(1000000,1,-1):
ok = True
for i in range(n):
if a[i][0] // k != a[i][1]:
ok = False
continue
if ok:
max_idx=k
break
print(min_idx,max_idx,sep=' ')
算法2
(二分查找) $O(logn)$
解释都注释在代码里了
n=int(input())
a=[]
for _ in range(n):
x,y=map(int,input().split())
a.append((x,y))
def check_min(x):
for i in range(0,n):
if a[i][1]<a[i][0]//x:#False即表示x太小了,即a[i][0]相对于a[i][1]大了,因此这里为大于号(注意,这里不能取等,取等的事情在二分中讨论)
return False
return True
def check_max(x):
for i in range(0,n):
if a[i][1]>a[i][0]//x:
return False#False即表示x太大(因为是求最大值,因此就应当假设X很大时,这个a[i][0]//x与a[i][1]的关系是什么,然后推导二分)了,即a[i][0]相对于a[i][1]小了,因此这里为大于号(注意,这里不能取等,取等的事情在二分中讨论)
return True
left_min,right_min,left_max,right_max=1,1000000000,1,1000000000
#当left<right没有等于号时
while left_min <right_min:
mid=(left_min+right_min)//2
if check_min(mid):
right_min=mid
else:
left_min = mid + 1
while left_max < right_max:
mid = (left_max + right_max+1) //2#求最大值的都是(l+r+1)//2,否则可能陷入无限循环
if check_max(mid):
left_max = mid
else:
right_max = mid-1
print(left_min,right_max,sep=' ')