โปรแกรมหาค่าสูงสุดที่น้อยที่สุดหลังจากดำเนินการ k ครั้งใน Python

สมมติว่ามีรายการตัวเลขชื่อ nums และค่า k ให้พิจารณาการดำเนินการที่ลบ 1 ออกจากสมาชิกใดก็ได้ในรายการ เราสามารถทำได้ k ครั้ง ต้องการหาค่าสูงสุดที่น้อยที่สุดในรายการหลังจากดำเนินการ k ครั้งดังกล่าว

ตัวอย่าง: nums = [3, 4, 6, 5], k = 6 ผลลัพธ์คือ 3 เพราะสามารถลด 4 ลง 1 ครั้ง, 6 ลง 3 ครั้ง, 5 ลง 2 ครั้ง ได้ [3, 3, 3, 3]

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

1. เรียง nums จากมากไปน้อย
2. กำหนด i = 0, curr = nums[0]
3. วนลูป بينما k > 0:
   • ขยับ i ขณะที่ nums[i] == curr
   • ถ้า k >= i:
     • k -= i
     • curr -= 1
   • มิฉะนั้น คืนค่า curr
4. คืนค่า curr

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums, k):
        nums.sort(reverse=True)
        i = 0
        curr = nums[0]
        while k > 0:
            while i < len(nums) and nums[i] == curr:
                i += 1
            if k >= i:
                k -= i
                curr -= 1
            else:
                return curr
        return curr

ob = Solution()
nums = [3, 4, 6, 5]
k = 6
print(ob.solve(nums, k))

อินพุต

[3, 4, 6, 5], 6

เอาต์พุต

3