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

สมมติว่ามีค่า n, index, maxSum ต้องหา nums[index] สูงสุดโดยอาร์เรย์ nums ต้องผ่านเงื่อนไข:

• ขนาด n
• ทุกค่าบวก
• |nums[i] - nums[i+1]| <= 1
• ผลรวมไม่เกิน maxSum
• nums[index] สูงสุด

ตัวอย่าง: n=6, index=3, maxSum=8 ผลลัพธ์ 2 (อาร์เรย์ [1,2,2,2,1,1])

วิธีแก้ปัญหา (Binary Search)

1. left := maxSum//n, right := maxSum+1, ans := 0
2. วน while left < right:
   • mid := left + (right-left)//2
   • คำนวณ ind_l (ผลรวมด้านซ้าย) และ ind_r (ด้านขวา) ของค่า mid ที่ดัชนี index
   • ถ้า ind_l + ind_r <= maxSum: ans = mid, left = mid+1
   • มิฉะนั้น: right = mid
3. คืน ans

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

def solve(n, index, maxSum):
    left, right = maxSum//n, maxSum+1
    ans = 0
    while left < right:
        mid = left + (right-left)//2
        ind_l = (mid-1+max(1,mid-index))*min(index,mid-1)//2 + abs(min(0,mid-index-1))
        ind_r = (mid+max(1,mid-(n-index-1)))*min(n-index,mid)//2 + abs(min(0,mid-(n-index-1)-1))
        if ind_l + ind_r <= maxSum:
            ans = mid
            left = mid+1
        else:
            right = mid
    return ans

n = 6
index = 3
maxSum = 8
print(solve(n, index, maxSum))

อินพุต

6, 3, 8

เอาต์พุต

2