传送门

给你一个下标从 0 开始大小为 m * n 的整数矩阵 values ，表示 m 个不同商店里 m * n 件不同的物品。每个商店有 n 件物品，第 i 个商店的第 j 件物品的价值为 values[i][j] 。除此以外，第 i 个商店的物品已经按照价值非递增排好序了，也就是说对于所有 0 <= j < n - 1 都有 values[i][j] >= values[i][j + 1] 。

每一天，你可以在一个商店里购买一件物品。具体来说，在第 d 天，你可以：

• 选择商店 i 。

• 购买数组中最右边的物品 j ，开销为 values[i][j] * d 。换句话说，选择该商店中还没购买过的物品中最大的下标 j ，并且花费 values[i][j] * d 去购买。

注意，所有物品都视为不同的物品。比方说如果你已经从商店 1 购买了物品 0 ，你还可以在别的商店里购买其他商店的物品 0 。

请你返回购买所有 m * n 件物品需要的 最大开销 。

难点在于开销通过values[i][j]*d计算，考虑排序不等式：

https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E4%B8%8D%E7%AD%89%E5%BC%8F/7775728

因此考虑贪心策略：每一次取当前可取的最小值

因为所有物品都可以取完，不存在局部最优解非全局最优解的情况。

Code:

class Solution {
public:
    long long maxSpending(std::vector<std::vector<int>>& values) {
        auto cp=[&](const std::pair<int,int>&l,const std::pair<int,int>&r){
            return l.first>r.first;
        };
        std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,decltype(cp)> priorityQueue(cp);
        for (int i = 0; i < values.size(); ++i) {
            priorityQueue.emplace(values[i].back(), i);
            values[i].pop_back();
        }
        long long day=1;
        long long max=0;
        while (!priorityQueue.empty()){
            auto[a,b]=priorityQueue.top();
            priorityQueue.pop();
            max+=a*day;
            day++;
            if (!values[b].empty()){
                priorityQueue.emplace(values[b].back(),b);
                values[b].pop_back();
            }
        }
        return max;
    }
};