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

สมมติว่าเรามีสามค่า n ดัชนี และ maxSum พิจารณาอาร์เรย์ที่เรียกว่า nums เราต้องหา nums[index] และ nums เป็นไปตามเงื่อนไขต่อไปนี้ -

• ขนาดของ nums คือ n

• องค์ประกอบทั้งหมดใน n เป็นค่าบวก

• |nums[i] - nums[i+1]| <=1 สำหรับ i, 0 <=i

• ผลรวมขององค์ประกอบทั้งหมดของ nums ไม่เกิน maxSum

• nums[index] ถูกขยายให้ใหญ่สุด

ดังนั้น หากอินพุตเป็น n =6, ดัชนี =3, maxSum =8 ผลลัพธ์จะเป็น 2 เพราะเราจะได้อาร์เรย์เช่น [1,2,2,2,1,1] ที่ตอบสนองได้ทั้งหมด เงื่อนไข และที่นี่ nums[3] ถูกขยายให้ใหญ่สุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ซ้าย :=ผลหารของ maxSum/n ขวา :=maxSum + 1

• ตอบ :=0

• ขณะที่ซ้าย <ขวา ทำ

  • กลาง :=ซ้าย + ผลหารของ (ขวา-ซ้าย)/2

  • ind_l :=(กลาง -1 + สูงสุด 1 และ (ดัชนีกลาง)) * ผลหารของ (ดัชนีต่ำสุดและ (กลาง-1) /2 + |ขั้นต่ำ 0, กลางดัชนี-1|

  • ind_r =(กลาง + สูงสุด 1 และ (กลาง-(n-index-1))) * ผลหารของ (ต่ำสุดของ (ดัชนี n) และกลาง)/2 + | ต่ำสุด 0 และ (กลาง-(ดัชนี n) -1)-1)|

  • ถ้า ind_l + ind_r <=maxSum แล้ว

    • ตอบ :=กลาง

    • ซ้าย :=กลาง+1

  • มิฉะนั้น

    • ขวา :=กลาง

• กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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