Chương trình đếm số vận động viên bơi lội có thể vô địch Python

Cho mảng nums điểm hiện tại của n vận động viên. Vòng chung kết: hạng 1 cộng n điểm, hạng 2 cộng n-1,... Hạng cuối cộng 1 điểm. Đếm số vận động viên vẫn có cơ hội vô địch (tính cả hòa đầu).

Ví dụ: nums=[9,6,11,12] → 3 (9, 11, 12 có thể vô địch).

Giải thuật

1. Sắp xếp nums
2. Tính a = max(nums[i] + n - i) cho i từ n-1 đến 0 (điểm tối đa có thể đạt được của ai đó)
3. Đếm số x trong nums thỏa x + n >= a (vẫn có thể đạt hoặc vượt a)

Ví dụ triển khai

def solve(nums):
    if not nums:
        return 0
    n = len(nums)
    ans = 0
    nums.sort()
    a = 0
    for i in range(n-1, -1, -1):
        cand = nums[i] + n - i
        if cand > a:
            a = cand
    for x in nums:
        if x + n >= a:
            ans += 1
    return ans

print(solve([9, 6, 11, 12]))

Đầu vào

[9, 6, 11, 12]

Đầu ra

3