2931 购买物品的最大开销

题目链接

2931. 购买物品的最大开销

分析

合并数组排序 或 贪心 + 最小堆

为了使得总开销最大，我们应该优先选择价值小的物品，有两种方法达成这一目的

1. 直接将所有数组合并，按递减序排序
2. 由于原数组已经按照递减序排序，我们可以使用类似632 最小区间的方法，将每个商店的最右侧值加入最小堆，动态维护最小值

以下介绍第二种方法的实现

我们首先将每个商店价值最小的商品加入最小堆中，每一天取出堆中价值最小的商品，并将该商品对应的商店的上一件商品加入最小堆中，动态维护最小值即可

代码实现

class Solution {
public:
    long long maxSpending(vector<vector<int>>& values) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        int m = values.size(), n = values[0].size();
        for(int i = 0; i < m; ++i)
        {
            pq.emplace(*values[i].rbegin(), i);
            values[i].pop_back();
        }
        long long ans = 0;
        for(int d = 1; d <= m * n; ++d)
        {
            auto [val, idx] = pq.top();
            pq.pop();
            ans += 1ll * d * val;  
            if(values[idx].size())
            {
                pq.emplace(*values[idx].rbegin(), idx);
                values[idx].pop_back();
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度
  • 合并数组：$O(nm \log(nm))$
  • 最小堆：$O(nm\log(m))$
• 空间复杂度
  • 合并数组：$O(nm)$
  • 最小堆：$O(m)$