สมมติว่าเรามีตัวเลขบวกสามตัวคือ n ล่าง และบน เราต้องหารายชื่อที่มีความยาวเป็น n และเพิ่มขึ้นเรื่อยๆ แล้วค่อยๆ ลดน้อยลง และตัวเลขทั้งหมดอยู่ในช่วง [ล่างและบน] (รวมทั้งสองอย่าง) และส่วนที่เพิ่มขึ้นและลดลงแต่ละส่วนไม่ควรว่างเปล่า เราต้องหารายการดังกล่าวที่ใหญ่ที่สุดเท่าที่จะเป็นไปได้ หากไม่สามารถทำได้ ให้ส่งคืนรายการว่าง
ดังนั้น หากอินพุตเป็น n =5 ล่าง =3 บน =7 ผลลัพธ์จะเป็น [6, 7, 6, 5, 4] หากเราสังเกตดีๆ ผลลัพธ์จะเป็น [7, 6, 5, 4, 3 ] ไม่ถูกต้องเนื่องจากส่วนที่เพิ่มขึ้นอย่างเคร่งครัดไม่ควรว่างเปล่า
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้า n> 2 * (บน - ล่าง) + 1 แล้ว
-
กลับรายการว่าง
-
-
c :=บน - ล่าง
-
ง :=1
-
ถ้า c
-
d :=n - c - 1
-
-
ถ้า d เท่ากับ 0 แล้ว
-
ง :=1
-
-
f :=รายการใหม่ตั้งแต่ช่วง (บน - d) ถึง (บน - 1)
-
g :=รายการใหม่จากช่วง (บน - n + d - 1) ลงสู่บน
-
เชื่อม f และ g แล้วกลับ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(n, lower, upper):
if n > 2 * (upper - lower) + 1:
return []
c = upper - lower
d = 1
if c < n:
d = n - c - 1
if d == 0:
d = 1
f = list(range(upper - d, upper))
g = list(range(upper, upper - n + d, -1))
return f + g
n = 5
lower = 3
upper = 7
print(solve(n, lower, upper)) อินพุต
5, 3, 7
ผลลัพธ์
[6, 7, 6, 5, 4]
