2412. Min Required Money

Minimum Money Required Before Transactions

本题被标记成Hard的原因 我后来注意到了

是因为破题关键在于 阅读测验

"Regardless of the order" of the transactions

题目中说我们得找出 在任何交易执行顺序下

都永远 『兵来将挡 水来土掩』 的最小金额

也就是这个金额 能确保不会在某笔交易完后

导致现有的钱 不够执行紧接著来的交易

各位不妨先停下来想 什么情况特别容易目睹

某笔交易结束后 手上剩馀的钱没法再去交易？

肯定是......经历了一连串的赔本交易

把初始资金不停蚕食鲸吞光 一点一点消耗

绝对安全感的防弹衣🪖

由前一段叙述来看 至少必须能够撑得住

所有赔钱交易的净亏损总额 因此我们

必须 把全部$cashback_i < cost_i$的交易搜出来

加总它们的亏损金额$L = \Sigma_i (cost_i - cashback_i)$

但是还得再加上净亏交易中的最大cashback$x$

Why?如果从开头就连续操作全部亏损交易

且最后一笔亏损交易 的cashback恰恰是$x$

本金累积被扣幅度最凶的时刻 便是 拿回$x$前的瞬间

可是还有赚钱的交易呢？

A. 若没任何赚钱的交易

题目要的100%最小安全金额 肯定就是上面说的 $L + x$

B. 而要是有赚钱的交易 就稍微要小心了

毕竟赔本的交易了结后 现在还有赚钱交易得干

赚钱交易的特性是每次结案 本金必不降

于是这时候我们只需要考虑一件事：

所有亏损交易消耗了我们后

还有足够的钱来付任何赚钱交易的入场费嘛？

毕竟赚钱交易 也不是天上掉馅饼

要先给出cost 才有cashback返还的

如何赚钱：🌫️守得云开见月明🌕

看到这儿 大家大概有猜到我们亦需要

$L + y$这个数字 $y$是所有赚钱交易中的最大cost

这个数字的话中话是：

如果运气最差 从开头就连续操作全部亏损交易

紧接著又撞见了入场费最贵的赚钱交易

那么我们一开始就得携带$L + y$这么多钱

才能搞定全部赚钱交易

毕竟后面的赚钱交易入场费肯定不超过$y$

而赚钱交易的定义又是结案后 本金绝对不降

于是现在就是要比较 $L + x$和$L + y$哪个更大

由更大的来作为我们最终的守护者

C++

#include <vector>
using namespace std;

long long calculateMinRequiredMoney(vector<vector<int>>& transactions) { // LeetCode Q.2412.
    long long totalAbsLoss = 0;

    int winningTradeMaxCost = -1;

    int losingTradeMaxCashback = -1;

    for (const auto& transaction : transactions) {
        int cost = transaction[0], cashback = transaction[1];

        if (cashback >= cost) {
            if (cost > winningTradeMaxCost)
                winningTradeMaxCost = cost;
            continue;
        }

        totalAbsLoss += cost - cashback;

        if (cashback > losingTradeMaxCashback)
            losingTradeMaxCashback = cashback;
    }

    long long minRequiredMoney = totalAbsLoss + losingTradeMaxCashback;

    if (winningTradeMaxCost == -1)
        return minRequiredMoney;

    if (minRequiredMoney < winningTradeMaxCost + totalAbsLoss)
        minRequiredMoney = winningTradeMaxCost + totalAbsLoss;

    return minRequiredMoney;
}

Python

def calculate_min_required_money(transactions: list[list[int]]) -> int:  # LeetCode Q.2412.
    total_abs_loss = 0

    losing_trade_max_cashback = -1
    winning_trade_max_cost = -1

    for cost, cashback in transactions:
        if cashback >= cost:
            if cost > winning_trade_max_cost:
                winning_trade_max_cost = cost
            continue

        abs_loss = cost - cashback
        total_abs_loss += abs_loss
        
        if cashback > losing_trade_max_cashback:
            losing_trade_max_cashback = cashback
    
    min_required_money = total_abs_loss + losing_trade_max_cashback
    
    if winning_trade_max_cost == -1: return min_required_money

    if min_required_money < winning_trade_max_cost + total_abs_loss:
        min_required_money = winning_trade_max_cost + total_abs_loss

    return min_required_money

时间复杂度：$O(n)$ 空间复杂度：$O(1)$

本题核心就在读懂"Regardless of the order"那句话