สมมติว่าเรามีสามค่า n, ผลรวม และ k ตอนนี้ให้พิจารณารายการของขนาด n ซึ่งมีผลรวมเท่ากับผลรวมและโดยที่ความแตกต่างที่แน่นอนระหว่างสององค์ประกอบที่ต่อเนื่องกันมากที่สุดคือ 1 เราต้องหาค่าสูงสุดที่ดัชนี k ของรายการดังกล่าว
ดังนั้น หากอินพุตเท่ากับ n =5 ทั้งหมด =15 k =3 ผลลัพธ์จะเป็น 4 เนื่องจากรายการที่เป็นไปได้อย่างใดอย่างหนึ่งคือ [3,2,3,4,3] องค์ประกอบสูงสุดที่พบในดัชนี 3 คือ 4.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- x :=0
- ทำสิ่งต่อไปนี้ซ้ำๆ ทำ
- a :=k + 1
- s :=(x + x - a + 1) * floor if a/2
- a :=n - k
- s :=s +(x + x - a + 1) * floor of a/2
- s :=s - x
- ถ้า s> ทั้งหมด แล้ว
- ออกมาจากลูป
- x :=x + 1
- ผลตอบแทน x - 1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(n, total, k): x = 0 while 1: a = k + 1 s = (x + x - a + 1) * a // 2 a = n - k s += (x + x - a + 1) * a // 2 s -= x if s > total: break x += 1 return x - 1 n = 5 total = 15 k = 3 print(solve(n, total, k))
อินพุต
5, 15, 3
ผลลัพธ์
4
