leetcode 3219. 切蛋糕的最小总开销 II

题目：3219. 切蛋糕的最小总开销 II - 力扣（LeetCode）

排序+贪心。

开销越大的越早切。

注意m或n为1的情况。

class Solution {
public:long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {long long ret = 0;sort(horizontalCut.begin(), horizontalCut.end());sort(verticalCut.begin(), verticalCut.end());long long a = 1, b = 1;long long h = 0;if (horizontalCut.size()) {h = horizontalCut[horizontalCut.size() - 1];horizontalCut.pop_back();}long long v = 0;if (verticalCut.size()) {v = verticalCut[verticalCut.size() - 1];verticalCut.pop_back();}long long hs = h * b;long long vs = v * a;while (h > 0 || v > 0) {if (h > v) {ret += hs;if (horizontalCut.empty()) {h = 0;} else {h = horizontalCut[horizontalCut.size() - 1];horizontalCut.pop_back();}a++;} else {ret += vs;if (verticalCut.empty()) {v = 0;} else {v = verticalCut[verticalCut.size() - 1];verticalCut.pop_back();}b++;}hs = h * b;vs = v * a;}return ret;}
};