โปรแกรมหาจำนวนรอบหมุนน้อยที่สุดเพื่อเพิ่มกำไรจากล้อฟีริสใน Python

ปัญหา

ล้อฟีริส 4 ตู้ ตู้ละ 4 คน หมุนทวนเข็มนาฬิกา ค่าใช้จ่ายต่อรอบ = run มีอาร์เรย์ cust จำนวนลูกค้ารอ ก่อนรอบที่ i ค่าโดยสารต่อคน = board (ต่อรอบ) ลูกค้าต้องขึ้นถ้ามีที่ว่าง หารอบหมุนน้อยที่สุดที่ทำกำไรสูงสุด

ตัวอย่าง

cust=[6,4], board=6, run=4 → ผลลัพธ์ 3 (รอบ1: 4 คนขึ้น, รอบ2: 4 คนขึ้น, รอบ3: 3 คนขึ้น; กำไร = 10*6 - 3*4 = 48)

ขั้นตอนการแก้ปัญหา

1. res := -1, mst := 0, tmp := 0, wt := 0
2. วน idx, val ใน cust:
   • wt += val
   • chg := min(4, wt)
   • wt -= chg
   • tmp += chg * board - run
   • ถ้า mst < tmp: res := idx+1, mst := tmp
3. x, y := divmod(wt, 4)
4. ถ้า 4*board > run: res += x
5. ถ้า y*board > run: res += 1
6. คืน res

การนำไปใช้งาน (Python)

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