阿里笔试题代码
def gcd(a, b):
if a<b:
a,b=b,a
while b:
a,b=b,a%b
return a
def f():
A, B, a, b = map(int, input().split())
if b == 0 or a==0:
print("0 0")
else:
g=gcd(a,b)
a//=g
b//=g
def binary_search(A,B,a,b,i,j):
while i<=j:
mid=(i+j)//2
if a*mid>A or b*mid>B:
j=mid-1
else:
i=mid+1
return j
j=binary_search(A,B,a,b,1,min(A,B))
j=max(j,0)
print(str(a*j) + " " + str(b*j))
# max_x=B*a//b
# max_y=A*b//b
# if max_x<max_y:
# for x in range(min(A + 1,max_x+1), 0, -g):
# y = b / a * x
# if y <= B and int(y) == y:
# print(str(x) + " " + str(int(y)))
# break
# else:
# for y in range(min(B + 1,max_y+1), 0, -g):
# x = a / b * y
# if x <= A and int(x) == x:
# print(str(x) + " " + str(int(y)))
# break
# f()
print(gcd(12,18))
def f():
T = int(input())
from collections import defaultdict,Counter
for _ in range(T):
n, m = map(int, input().split())
path = [[float('inf') for _ in range(n)] for _ in range(n)]
for _ in range(m):
s, e, c = list(map(int, input().split()))
path[s][e] = c
path[e][s] = c
q = int(input())
qs = []
for _ in range(q):
qs.append(int(input()))
for i in range(n):
for j in range(n):
for k in range(n):
if i == j or j == k or i == k: continue
if path[i][k] != float('inf') and path[k][j] != float('inf'):
path[i][j] = min(path[i][j], max(path[i][k], path[k][j]))
c=[]
for i in range(n):
for j in range(n):
if path[i][j]!=float('inf'):
c.append(path[i][j])
c=sorted(c)
# print(c)
def binary_search(l,r,q):
while l<=r:
mid=(l+r)//2
if c[mid]<q:l=mid+1
else:r=mid-1
return l
for q in qs:
print(len(c)-binary_search(0,len(c)-1,q))
f()
"""
2
2 1
0 1 2
3
1
2
3
3 3
0 1 2
0 2 4
1 2 5
5
0
2
3
4
5
2
2
0
6
6
4
4
0
"""
全部评论
(2) 回帖