3219. Minimum Cost for Cutting Cake II

#define ll long long
class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)
    {
        // 因為會越切越多塊，所以 cost 要由大往小排
        sort(horizontalCut.begin(), horizontalCut.end(), greater<int>());
        sort(verticalCut.begin(), verticalCut.end(), greater<int>());

        int hPieces = 0, vPieces = 0;
        ll minCost = 0;

        while (hPieces < m - 1 && vPieces < n - 1)
        {
            if (horizontalCut[hPieces] > verticalCut[vPieces])
            {
                minCost += horizontalCut[hPieces++] * (vPieces + 1);
            }
            else
            {
                minCost += verticalCut[vPieces++] * (hPieces + 1);
            }
        }

        while (hPieces < m - 1)
        {
            minCost += horizontalCut[hPieces++] * (vPieces + 1);
        }

        while (vPieces < n - 1)
        {
            minCost += verticalCut[vPieces++] * (hPieces + 1);
        }
        return minCost;
    }
};

• T: $O((m + n) \cdot \log (m + n))$
• S: $O(M + N)$