โปรแกรมนับจำนวนนักว่ายน้ำที่จะชนะรอบสุดท้ายใน Python

สมมติว่าเรามีรายการตัวเลขชื่อ nums ความยาว n สมาชิกแทนคะแนนปัจจุบันของนักว่ายน้ำในการแข่งขัน สำหรับรอบสุดท้าย อันดับหนึ่งรอบนี้ได้ n คะแนน อันดับสองได้ n-1 คะแนน และต่อไป เราต้องตรวจสอบจำนวนนักว่ายน้ำที่ยังคงมีโอกาสชนะในรอบสุดท้ายหลังรอบปัจจุบัน หากคะแนนเท่ากันอันดับหนึ่ง นับว่าเป็นการชนะด้วย

เช่น ถ้าอินพุตคือ nums = [9, 6, 11, 12] ผลลัพธ์จะเป็น 3 เพราะนักว่ายน้ำที่มีคะแนน 9, 11 และ 12 ทุกคนชนะได้ หากคะแนนสุดท้ายเป็น [13, 9, 13, 13] นักว่ายน้ำคะแนน 9 ได้อันดับหนึ่งเพิ่ม 4 คะแนน คะแนน 6 ได้อันดับสองกลายเป็น 9 คะแนน 11 ได้อันดับสามกลายเป็น 13 คะแนน 12 ได้อันดับสี่คะแนน 12 แต่แม้ 6 จะได้อันดับหนึ่งคะแนนสุดท้าย 10 ก็ยังไม่มีโอกาสชนะ

ขั้นตอนการแก้ปัญหา

1. ถ้า nums ว่าง คืนค่า 0
2. n := ขนาดของ nums, ans := 0
3. เรียงลำดับ nums
4. a := 0
5. สำหรับ i ในช่วง n-1 ลงถึง 0:
   • cand := nums[i] + n - i
   • ถ้า cand > a ให้ a := cand
6. สำหรับแต่ละ x ใน nums:
   • ถ้า x + n >= a ให้ ans += 1
7. คืนค่า ans

ตัวอย่างการใช้งาน

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

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

อินพุต

[9, 6, 11, 12]

เอาต์พุต

3