Giả sử có một vòng đu quay có bốn cabin và mỗi cabin có thể chứa bốn hành khách. Bánh xe quay ngược chiều kim đồng hồ, và mỗi vòng quay, nó sẽ tốn một lượng tiền 'chạy'. Bây giờ chúng ta có một mảng 'mãng cầu' chứa n mục và mỗi mục tôi biểu thị số người đang chờ để được vào vòng đu quay trước vòng quay thứ i. Để lên được bánh xe, mỗi khách hàng phải trả một khoản tiền 'lên xe', và số tiền đó là cho một lần quay ngược chiều kim đồng hồ của bánh xe. Những người xếp hàng chờ đợi không nên đợi nếu trong bất kỳ cabin nào còn chỗ trống. Vì vậy, với dữ liệu, chúng tôi phải tìm ra số lượng quay vòng tối thiểu cần thiết để lợi nhuận có thể được tối đa hóa.
Vì vậy, nếu đầu vào giống như cust =[6,4], board =6, run =4, thì đầu ra sẽ là 3
Lúc đầu, 6 người đang xếp hàng chờ. Vì vậy, ban đầu 4 người vào khoang đầu tiên, những người còn lại đợi khoang tiếp theo.
Bánh xe quay, và cabin thứ hai đến. Trong khi đó, 4 người nữa vào hàng. Vì vậy, 4 người tiếp theo đang chờ được vào khoang tiếp theo.
Bánh xe quay trở lại và ba khách hàng còn lại vào cabin tiếp theo.
Vì vậy, cần tối thiểu ba vòng quay để phục vụ tất cả khách hàng.
Lợi nhuận tối đa có thể đạt được từ các vòng quay này là (10 * 6) - (3 * 4) =48.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
res:=-1
-
mst:=0
-
tmp:=0
-
wt:=0
-
cho mỗi idx chỉ mục và giá trị val trong cust, thực hiện
-
wt:=wt + val
-
chg:=tối thiểu là (4, wt)
-
wt:=wt - chg
-
tmp:=tmp + chg * board - run
-
nếu mst
-
res:=idx + 1
-
mst:=tmp
-
-
-
x:=wt / 4
-
y:=wt mod 4
-
if 4 * board> run, then
-
res:=res + x
-
-
if y * board> run, then
-
res:=res + 1
-
-
trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
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