Chương trình tìm số vòng quay tối thiểu để tối đa lợi nhuận xe quay trong Python

Xe quay 4 buồng, mỗi buồng 4 khách. Mảng cust[i] = khách chờ trước vòng i. Mỗi khách trả board, mỗi vòng tốn run. Khách không chờ nếu có chỗ trống. Tìm số vòng nhỏ nhất để lợi nhuận tối đa.

Ví dụ: cust=[6,4], board=6, run=4 → 3 vòng. Lợi nhuận max = 10*6 - 3*4 = 48.

Giải thuật (Mô phỏng + tối ưu vòng cuối)

1. Mô phỏng từng vòng trong cust: cập nhật khách chờ wt, lên xe chg = min(4, wt), cập nhật lợi nhuận tích lũy tmp, theo dõi max mst và vòng res.
2. Sau mảng cust, còn wt khách chờ. Tính thêm: mỗi 4 khách cho 1 vòng nếu 4*board > run; khách lẻ y thêm 1 vòng nếu y*board > run.
3. Trả về res.

Ví dụ minh họa

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))

Đầu vào

[6,4], 6, 4

Đầu ra

3