LeetCode-1599 Maximum Profit of Operating a Centennial Wheel

Description

你正在经营一座摩天轮，该摩天轮共有 4 个座舱，每个座舱最多可以容纳 4 位游客。你可以逆时针轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。摩天轮每次轮转都恰好转动 1 / 4 周。

给你一个长度为 n 的数组 customers ， customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 i 次。每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。

你可以随时停下摩天轮，即便是在服务所有游客之前。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转。注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待下一次轮转。

返回最大化利润所需执行的最小轮转次数。如果不存在利润为正的方案，则返回 -1 。

Constraints

\(1 \le n \le 10^5\)
\(0 \le customers_i \le 50\)
\(1 \le boardingCost, runningCost \le 100\)

Solution

题面很复杂（这次不化简描述了），但做法很简单。

有4位客人就塞进去，不足的话只能勉强上。每一轮的贡献都比较一下谁最优即可。

~~解法不是最优解，胜在简单。~~时间复杂度\({O(\frac{50}{4}n)}\)。

改成最优解了，\(O(n)\)。

Code

class Solution {
public:
    int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {
        // sum of available customers
        int sum = 0;
        int profit = 0;
        int cur = 0;

        // {profit, rev-times}
        tuple<int, int> best {0, 1};

        auto fetch = [&](int batch = 1) {
            int board = min(4 * batch, sum);
            sum -= board;
            profit += board * boardingCost - batch * runningCost;
            cur += batch;

            auto cmp = make_tuple(profit, -cur);
            if(cmp > best) best = cmp;
        };

        for(auto &c : customers) {
            sum += c;
            fetch();
        }

        if(sum) {
            // %4 == 0
            // batch==0 has no effect
            int batch = sum / 4;
            fetch(batch);

            // fallthrough
            // %4 != 0
            fetch();
        }

        auto [_, rt] = best;
        return -rt;
    }
};

Link

LeetCode-1599 Maximum Profit of Operating a Centennial Wheel