简答题 偏难
#5782

过马路问题 在遥远的mars星球,即将入学的小精灵们正在学习过马路。它们需要请精灵学院的哥哥姐姐们的指导。 精灵学院共有C名学员(1≤C≤2000),编号为1.…

过马路问题

在遥远的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)

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>参考程序:</p><pre class="brush:python;toolbar:false">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]&gt;a[j]) or (a[i]==a[j] and b[i]&gt;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]&gt;=a[i] and t[j]&lt;=b[i] and h[j]==0): ans=ans+1 h[j]=1 break if(t[j]&gt;b[i]): break print(ans)</pre>
解析

评分标准:

(1)x,y或等效答案;(2分)

(2)sort()或等效答案;(3分)

(3)b[i],b[j]=b[j],b[i]或等效答案;(2分)

(4)ans=ans+1或等效答案。(3分)