สมมติว่าเรามีค่า n และรายการคู่อื่นที่เรียกว่าข้อจำกัด เราต้องการสร้าง n อาคารใหม่ในเมือง แต่มีข้อจำกัดเล็กน้อย เราสามารถสร้างเส้นและอาคารที่มีป้ายกำกับตั้งแต่ 1 ถึง n ข้อจำกัดมีสองพารามิเตอร์ ดังนั้นข้อ จำกัด[i] =(id_i, max_height_i) แสดงว่า id_i ต้องมีความสูงน้อยกว่าหรือเท่ากับ max_height_i ข้อจำกัดของเมืองเกี่ยวกับความสูงของอาคารใหม่มีดังนี้ -
-
ความสูงของอาคารแต่ละหลังต้องเป็น 0 หรือค่าบวก
-
ความสูงของอาคารแรกต้องเป็น 0
-
ความแตกต่างระหว่างความสูงของอาคารสองหลังที่อยู่ติดกันต้องไม่เกิน 1
เราต้องหาความสูงสูงสุดของตึกที่สูงที่สุดให้ได้
ดังนั้นหากอินพุตเป็น n =5 ข้อจำกัด =[2,1],[4,3]] ผลลัพธ์จะเป็น 4 เพราะเราต้องหาความสูงสูงสุดที่เป็นไปได้จึงได้ 4 ดังแสดงใน แผนภาพ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
หากข้อจำกัดว่างเปล่า
-
กลับ n-1
-
-
resi :=จัดเรียงข้อ จำกัด ของรายการตาม id
-
k :=0
-
idx :=1
-
สำหรับแต่ละ re ใน resi ทำ
-
re[1] :=ขั้นต่ำของ re[1] และ (k+re[0]-idx)
-
k :=re[1]
-
idx :=re[0]
-
-
k :=ความสูงสูงสุดขององค์ประกอบสุดท้ายใน resi
-
idx :=id ขององค์ประกอบสุดท้ายใน resi
-
ย้อนกลับรายการ resi
-
สำหรับแต่ละ re in resi ตั้งแต่ข้อแรกเป็นต้นไป ทำ
-
re[1] :=ขั้นต่ำของ re[1] และ (k-re[0]+idx)
-
k :=re[1]
-
idx :=re[0]
-
-
ย้อนกลับรายการ resi
-
ฉ :=0
-
idx :=1
-
res :=0
-
สำหรับแต่ละ re ใน resi ทำ
-
ff :=ขั้นต่ำของ (f+re[0]-idx) และ re[1]
-
res :=สูงสุดของความละเอียดและผลหารของ (re[0] - idx + f + ff)/2
-
idx :=re[0]
-
f :=ff
-
-
คืนค่าสูงสุดของ (f+n-idx) และ res
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(n, restrictions):
if not restrictions:
return n-1
resi = sorted(restrictions, key = lambda x:x[0])
k = 0
idx = 1
for re in resi:
re[1] = min(re[1], k+re[0]-idx)
k = re[1]
idx = re[0]
k = resi[-1][1]
idx = resi[-1][0]
resi.reverse()
for re in resi[1:]:
re[1] = min(re[1], k-re[0]+idx)
k = re[1]
idx = re[0]
resi.reverse()
f = 0
idx = 1
res = 0
for re in resi:
ff = min(f+re[0]-idx, re[1])
res = max(res, (re[0] - idx + f + ff) // 2)
idx = re[0]
f = ff
return max(f+n-idx,res)
n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions)) อินพุต
5, [[2,1],[4,3]]
ผลลัพธ์
4
