超过时限

Question

有N名车手参加锦标赛。它们都是在每次比赛后分配的分数，包括决赛。比赛的获胜者得N分，亚军得N-1分，依此类推，直到最后一名车手得1分为止。两名车手不可能在同一地点完成一场比赛

编写一个程序，根据每个车手在最后一场比赛前获得的总积分，计算有多少车手在最后一场比赛后仍有机会获得最大的总积分，从而赢得冠军。如果不止一名车手拥有相同的最高积分，他们都将获得世界冠军头衔

我的所有测试用例都超过了时间限制，我的代码在一个测试用例（100名参与者）中失败。 测试用例包括：

测试用例1:
3
10
9
8
输出-3
测试用例2:
5
15
14
12
14
15
输出-4
这是我的密码：

n=int(input())
b=[]
for i in range(n) :
    b.append(int(input()))
l=len(b)
c=l
sort(b)-->>> some sorting algo to sort in O(n*logn)
for i in range(len(b)) :
    x=b[i]
    x+=l
    for j in range(i+1,len(b)) :
        l-=1
        y=b[j]
        y+=l
        if y>x :
            c-=1
            break
print(c)``

Answer 1

如果事情过于复杂，可以用O（NlogN）轻松解决，假设results是驱动程序的当前结果，而N是驱动程序的数量。你所要做的就是：

N = 5
results = [ 15, 14, 12, 14, 15 ]
# find who can achieve the highest result
max_points = max([a+b for a,b in enumerate(sorted(results, reverse=True))])
# now count how many drivers can get as much as "max_points"
has_potential = [ 1 for r in results if r+N-1 >= max_points ]
print len(has_potential)   # print the result

输出：

4