Minimum Money Required Before Transactions

You are given a 0-indexed 2D integer array transactions , where transactions[i] = [costi, cashbacki] .

The array describes transactions, where each transaction must be completed exactly once in some order. At any given moment, you have a certain amount of money . In order to complete transaction $i$, $money \geq {cost}_i$ must hold true. After performing a transaction, money becomes $money - {cost}_i + {cashback}_i$.

Return the minimum amount of money required before any transaction so that all of the transactions can be completed regardless of the order of the transactions.

Example 1:

Input: transactions = [[2,1],[5,0],[4,2]]
Output: 10
Explanation:
Starting with money = 10, the transactions can be performed in any order.
It can be shown that starting with money < 10 will fail to complete all transactions in some order.

Example 2:

Input: transactions = [[3,0],[0,3]]
Output: 3
Explanation:
- If transactions are in the order [[3,0],[0,3]], the minimum money required to complete the transactions is 3.
- If transactions are in the order [[0,3],[3,0]], the minimum money required to complete the transactions is 0.
Thus, starting with money = 3, the transactions can be performed in any order.

解题思路

　　对于某种顺序确定后如何求最大值呢，假设已经完成了前$i-1$笔交易，那么第$i$笔的交易应该要满足$$\mathrm{money} - (a_0 - b_0) - (a_1 - b_1) - \cdots - (a_{i-1} - b_{i-1}) \geq a_i$$即$$\mathrm{money} \geq (a_0 - b_0) + (a_1 - b_1) + \cdots + (a_{i-1} + b_{i-1}) + a_i$$

　　$\mathrm{money}$要取最小值，那么就要遍历所有情况，取不等式右边的最大值。那么最大值会出现在哪一种情况呢，从集合的角度来看，根据$a_i$的不同把方案分成若干个集合，不等式右边的最大值一定会在其中一个集合出现。接着枚举$a_i$，当$a_i$固定后，要使得右式取最大值等价于求$(a_0 - b_0) + (a_1 - b_1) + \cdots + (a_{i-1} + b_{i-1})$的最大值，当每一项都是正数时，即$a_k - b_k > 0$，就可以取到最大值。因此一开始可以枚举 transactions 数组，把$a_k - b_k > 0$的交易累加，就可以取到最大值，然后枚举$a_i$，如果有$a_i - b_i > 0$那么总和减去$a_i - b_i$再加上$a_i$就可以快速算出不等式右边的值。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     long long minimumMoney(vector<vector<int>>& transactions) {
 4         long long sum = 0;
 5         for (auto &p : transactions) {
 6             if (p[0] - p[1] > 0) sum += p[0] - p[1];
 7         }
 8         long long ret = 0;
 9         for (auto &p : transactions) {
10             long long t = sum;
11             if (p[0] - p[1] > 0) t -= p[0] - p[1];
12             ret = max(ret, t + p[0]);
13         }
14         return ret;
15     }
16 };

参考资料

　　y总，第一名是谁，可以讲一下第一名的代码吗？力扣第87场双周赛：https://www.bilibili.com/video/BV1FV4y1u79H