Leetcode3219. 切蛋糕的最小总开销 II

Every day a Leetcode

题目来源：3219. 切蛋糕的最小总开销 II

解法1：贪心

谁的开销更大，就先切谁，并且这个先后顺序与切的次数无关。

代码：

/** @lc app=leetcode.cn id=3219 lang=cpp** [3219] 切蛋糕的最小总开销 II*/// @lc code=start
class Solution
{
public:long long minimumCost(int m, int n, vector<int> &horizontalCut, vector<int> &verticalCut){sort(horizontalCut.begin(), horizontalCut.end(), greater<int>());sort(verticalCut.begin(), verticalCut.end(), greater<int>());long long ans = 0;int cnt_h = 1, cnt_v = 1;int i = 0, j = 0;while (i < m - 1 || j < n - 1){if (j == n - 1 || i < m - 1 && horizontalCut[i] > verticalCut[j]){ans += horizontalCut[i++] * cnt_h; // 横切cnt_v++;                           // 需要竖切的蛋糕块增加}else{ans += verticalCut[j++] * cnt_v; // 竖切cnt_h++;                         // 需要横切的蛋糕块增加}}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(mlogm+nlogn)，瓶颈在排序上。

空间复杂度：O(1)。