สมมติว่ามีชิงช้าสวรรค์ที่มีห้องโดยสารสี่ห้อง และแต่ละห้องโดยสารสามารถมีผู้โดยสารได้สี่คน วงล้อหมุนทวนเข็มนาฬิกา และสำหรับการหมุนแต่ละครั้ง จะต้องใช้เงินจำนวน 'วิ่ง' ตอนนี้เรามีอาร์เรย์ 'cust' ที่มี n รายการ และแต่ละรายการ i หมายถึงจำนวนคนที่รอเข้าชิงช้าสวรรค์ก่อนการหมุนครั้งที่ i ในการขึ้นกระเช้า ลูกค้าแต่ละรายจะต้องจ่ายเงิน 'กระดาน' เป็นจำนวนเงิน และเงินจำนวนนั้นใช้สำหรับการหมุนวงล้อทวนเข็มนาฬิกาหนึ่งครั้ง ผู้คนที่รอเข้าแถวไม่ควรรอหากมีที่นั่งว่างในห้องโดยสาร จากข้อมูลนี้ เราต้องหาจำนวนการหมุนขั้นต่ำที่จำเป็นเพื่อจะได้กำไรสูงสุด
ดังนั้นหากอินพุตเป็นเหมือน cust =[6,4], board =6, run =4 เอาต์พุตจะเป็น 3
ตอนแรกรอคิวอยู่ 6 คน ดังนั้นในตอนแรก 4 คนจะเข้าไปในห้องโดยสารแรก และที่เหลือจะรอห้องโดยสารถัดไป
ล้อหมุนและห้องโดยสารที่สองก็มาถึง ในขณะเดียวกัน มีอีก 4 คนเข้าแถว ดังนั้นอีก 4 คนที่รออยู่จะได้เข้าไปในห้องโดยสารถัดไป
วงล้อหมุนอีกครั้ง และลูกค้าอีกสามคนที่เหลือจะเข้าไปในห้องโดยสารถัดไป
ดังนั้น อย่างน้อยที่สุดก็ต้องมีการหมุนเวียนสามครั้งเพื่อให้บริการลูกค้าทุกคนได้
กำไรสูงสุดที่ทำได้จากการหมุนเวียนเหล่านี้คือ (10 * 6) - (3 * 4) =48
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
res :=-1
-
mst :=0
-
tmp :=0
-
wt :=0
-
สำหรับแต่ละดัชนี idx และ val ค่าใน cust ทำ
-
wt :=wt + วาล
-
chg :=ขั้นต่ำ (4, wt)
-
wt :=wt - chg
-
tmp :=tmp + chg * บอร์ด - รัน
-
ถ้า mst
-
res :=idx + 1
-
mst :=tmp
-
-
-
x :=wt / 4
-
y :=wt mod 4
-
ถ้า 4 * บอร์ด> วิ่ง แล้ว
-
res :=res + x
-
-
ถ้า y * บอร์ด> วิ่ง แล้ว
-
res :=res + 1
-
-
ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(cust, board, run):
res = -1
mst = 0
tmp = 0
wt = 0
for idx, val in enumerate(cust):
wt += val
chg = min(4, wt)
wt -= chg
tmp += chg * board - run
if mst < tmp:
res, mst = idx+1, tmp
x, y = divmod(wt, 4)
if 4 * board > run:
res += x
if y * board > run:
res += 1
return res
print(solve([6,4], 6, 4)) อินพุต
[6,4], 6, 4
ผลลัพธ์
3
