题目：
给你一个下标从 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 件物品需要的 最大开销 。
示例 1：
输入：values = [[8,5,2],[6,4,1],[9,7,3]]
输出：285
解释：第一天，从商店 1 购买物品 2 ，开销为 values[1][2] * 1 = 1 。
第二天，从商店 0 购买物品 2 ，开销为 values[0][2] * 2 = 4 。
第三天，从商店 2 购买物品 2 ，开销为 values[2][2] * 3 = 9 。
第四天，从商店 1 购买物品 1 ，开销为 values[1][1] * 4 = 16 。
第五天，从商店 0 购买物品 1 ，开销为 values[0][1] * 5 = 25 。
第六天，从商店 1 购买物品 0 ，开销为 values[1][0] * 6 = 36 。
第七天，从商店 2 购买物品 1 ，开销为 values[2][1] * 7 = 49 。
第八天，从商店 0 购买物品 0 ，开销为 values[0][0] * 8 = 64 。
第九天，从商店 2 购买物品 0 ，开销为 values[2][0] * 9 = 81 。
所以总开销为 285 。
285 是购买所有 m * n 件物品的最大总开销。
示例 2：
输入：values = [[10,8,6,4,2],[9,7,5,3,2]]
输出：386
解释：第一天，从商店 0 购买物品 4 ，开销为 values[0][4] * 1 = 2 。
第二天，从商店 1 购买物品 4 ，开销为 values[1][4] * 2 = 4 。
第三天，从商店 1 购买物品 3 ，开销为 values[1][3] * 3 = 9 。
第四天，从商店 0 购买物品 3 ，开销为 values[0][3] * 4 = 16 。
第五天，从商店 1 购买物品 2 ，开销为 values[1][2] * 5 = 25 。
第六天，从商店 0 购买物品 2 ，开销为 values[0][2] * 6 = 36 。
第七天，从商店 1 购买物品 1 ，开销为 values[1][1] * 7 = 49 。
第八天，从商店 0 购买物品 1 ，开销为 values[0][1] * 8 = 64 。
第九天，从商店 1 购买物品 0 ，开销为 values[1][0] * 9 = 81 。
第十天，从商店 0 购买物品 0 ，开销为 values[0][0] * 10 = 100 。
所以总开销为 386 。
386 是购买所有 m * n 件物品的最大总开销。
提示：
1 <= m == values.length <= 101 <= n == values[i].length <= 1041 <= values[i][j] <= 106values[i]按照非递增顺序排序。
思路：
根据贪心算法，我们肯定是在天数小(d小)的时候选择价值小的商品，这样天数大的时候，价值高的商品能带来的开销更多。
所以我们可以利用优先级队列寻求 全部商店 可以购买的商品中 价值最小的。这次购置它，然后将这个商店中可购买的下一个商品入队。一直到所有商品都购置完，就是答案
代码：
class Solution {
public:
bool valid(vector<int>& idx) {
for (long long i = 0; i < idx.size(); i++) {
if (idx[i] >= 0) return true;
}
return false;
}
long long maxSpending(vector<vector<int>>& values) {
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
long long ans = 0;
int m = values.size(), n = values[0].size();
vector<int> idx(m, n - 1);
for (int i = 0; i < m; i++) {
pq.push(make_pair(values[i][n - 1], i));
}
long long day = 1;
while (true) {
auto top = pq.top();
pq.pop();
ans += top.first * day;
day++;
idx[top.second]--;
if (!valid(idx)) break;
if (idx[top.second] >= 0) pq.push(make_pair(values[top.second][idx[top.second]], top.second));
}
return ans;
}
};