用 Python 编写程序，找出使摩天轮利润最大化所需的最少旋转次数

pythonserver side programmingprogramming更新于 2025/11/30 13:00:17

假设有一个摩天轮，有四个舱室，每个舱室可容纳四名乘客。轮子逆时针旋转，每旋转一次，需要花费"run"金额。我们现在有一个包含 n 个项目的数组"cust"，每个项目 i 表示在第 i 次旋转之前等待进入摩天轮的人数。要登上摩天轮，每位顾客必须支付一定金额的"board"，这笔钱用于轮子逆时针旋转一次。如果任何舱室有空位，排队等候的人就不应该等待。因此，给定数据，我们必须找出所需的最小旋转次数，以便实现利润最大化。

因此，如果输入为 cust = [6,4], board = 6, run = 4，则输出为 3

起初，有 6 个人在排队。因此，最初有 4 个人进入第一个舱室，其余人等待下一个舱室。

轮子转动，第二个舱室到达。与此同时，又有 4 个人进入队列。因此，接下来等待的 4 个人将进入下一个舱室。

轮子再次旋转，剩下的 3 名顾客将进入下一个舱室。

因此，至少需要旋转三次才能服务所有顾客。

这些旋转可实现的最大利润为 (10 * 6) - (3 * 4) = 48。

为了解决这个问题，我们将遵循以下步骤 −

res := -1
mst := 0
tmp := 0
wt := 0
对于 cust 中的每个索引 idx 和值 val，执行
- wt := wt + val
- chg := (4, wt) 的最小值
- wt := wt - chg
- tmp := tmp + chg * board - run
- 如果 mst < tmp，则
  - res := idx + 1
  - mst := tmp
x := wt / 4
y := wt mod 4
如果 4 * board >运行，然后
- res := res + x
如果 y * board > run，则
- res := res + 1
返回 res

示例

让我们看看下面的实现以便更好地理解

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