A24941. 过马路问题在遥远的mars星球，即将入学的小精灵们正在学习过马路。它们需要请精灵学院的哥哥姐姐们的指导。精灵学院共有C名学员（1≤C≤2000），编号为1...C，每名学员i愿意在时间Ti帮助小精灵。当前共有N名小精灵（1≤N≤2000），编号为1...N，其中小精灵j能够在时间Aj和时间Bj之间过马路。当前情况下，结伴过马路是最好的办法，每位小精灵j想找到一位学员i结伴过马路，i和j必须满足A…
填空题
困难
知识点
题目描述
过马路问题
在遥远的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)参考答案
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):
x,y= map(int, input().split())
a.append(x)
b.append(y)
t.sort()
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]
b[i],b[j]=b[j],b[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):
ans=ans+1
h[j]=1
break
if(t[j]>b[i]):
break
print(ans)答案解析
评分标准：
（1）x,y或等效答案；（2分）
（2）sort()或等效答案；（3分）
（3）b[i],b[j]=b[j],b[i]或等效答案；（2分）
（4）ans=ans+1或等效答案。（3分）
上一题
下一题