过马路问题
在遥远的mars星球，即将入学的小精灵们正在学习过马路。它们需要请精灵学院的哥哥姐姐们的指导。
精灵学院共有C名学员（1≤C≤2000），编号为1...C，每名学员i愿意在时间Ti帮助小精灵。当前共有N名小精灵（1≤N≤2000），编号为1...N，其中小精灵j能够在时间Aj和时间Bj之间过马路。当前情况下，结伴过马路是最好的办法，每位小精灵j想找到一位学员i结伴过马路，i和j必须满足Aj≤Ti≤Bj。
每名学员最多只能结伴一名小精灵，每名小精灵最多结伴一名学员，请帮助计算可以得到的最大结伴数。
输入格式：
第一行输入包含C和N。
接下来C行包含T1 ... TC，
再接下来N行包含用于j = 1 ... N的Aj和Bj（Aj≤Bj）。 A，B和T都是不超过30000的正整数。
输入样例：
5 4 7 8 6 2 9 2 5 4 9 0 3 8 13
输出格式：
一共整数，表示精灵学院学员和小精灵的最大结伴数。
输出样例：
3
n,m= map(int, input().split())
t=[];a=[];b=[];h=[]
for i in range(1,n+1):
x=int(input())
t.append(x)
h.append(0)
for i in range(1,m+1):
① = map(int, input().split())
a.append(x)
b.append(y)
t. ②
for i in range(m-1):
for j in range(m):
if((a[i]>a[j]) or (a[i]==a[j] and b[i]>b[j])):
a[i],a[j]=a[j],a[i]
③
ans=0
for i in range(m):
for j in range(n):
if(t[j]>=a[i] and t[j]<=b[i] and h[j]==0):
④
h[j]=1
break
if(t[j]>b[i]):
break
print(ans)
相似题推荐
埃氏筛中将内层循环从j = i*i 开始而不是j = 2*i 的主要原因是（）。
def eratosthenes_sieve_for(n): if n < 2: return [] is_composite = [False] * (n + 1) primes = [] for i in range(2, n + 1): if is_composite[i]: continue primes.append(i) # 用for循环模拟C++的 j = i*i; j <=n; j +=i for j in range(i * i, n + 1, i): is_composite[j] = True return primes
| A． 因为2*i 一定不是合数 |
B． i*i 一定是质数 |
| C． 小于i*i 的i 的倍数已被更小质因子筛过 |
D． 这样可以把时间复杂度降为O(n) |
对如下代码实现的欧几里得算法（辗转相除法），调用gcd(48 , 18) 得到的调用序列为（）。
def gcd(a, b): if b == 0: return a else: return gcd(b, a % b)
| A．gcd(48 ,18) -> gcd(18 ,12) -> gcd(12 ,6) -> gcd(6 ,0) | B．gcd(48 ,18) -> gcd(30 ,18) -> gcd(12 ,18) |
| C．gcd(48 ,18) -> gcd(18 ,30) -> gcd(30 ,6) | D．gcd(48 ,18) -> gcd(12 ,18) -> gcd(6 ,12) |
下面代码用分治求“最大连续子段和”，其时间复杂度为（）。
import sys def solve(a , l , r): if l == r: return a [l] mid = l + (r - l) // 2 left = solve(a , l , mid) right = solve(a , mid + 1 , r) sum_val = 0 lmax = -sys .maxsize - 1 for i in range(mid , l - 1 , -1): sum_val += a [i] lmax = max (lmax , sum_val) sum_val = 0 rmax = -sys .maxsize - 1 for i in range(mid + 1 , r + 1): sum_val += a [i] rmax = max (rmax , sum_val) return max(left , right , lmax + rmax) if __name__ == "__main__": a1 = [-2 , 1 , -3 , 4 , -1 , 2 , 1 , -5 , 4] print(solve(a1 , 0 , len(a1)-1)) a2 = [-5 , -3 , -1 , -4] print(solve(a2 , 0 , len(a2)-1)) a3 = [10] print(solve(a3 , 0 , 0))
| A． O(n2) |
B． O(nlogn) |
| C． O(logn) |
D． O(n) |
