class Solution {
public:
long long maxSpending(vector<vector<int>>& values) {
}
};
2931. 购买物品的最大开销
给你一个下标从 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] 按照非递增顺序排序。原站题解
golang 解法, 执行用时: 120 ms, 内存消耗: 8.2 MB, 提交时间: 2023-11-13 20:49:40
func maxSpending(values [][]int) int64 {
m, n := len(values), len(values[0])
id := make([]int, m)
for i := range id {
id[i] = i
}
h := &hp{id, values}
heap.Init(h)
ans := 0
for d := 1; d <= m*n; d++ {
a := values[id[0]]
ans += a[len(a)-1] * d
if len(a) > 1 {
values[id[0]] = a[:len(a)-1]
heap.Fix(h, 0)
} else {
heap.Pop(h)
}
}
return int64(ans)
}
type hp struct {
sort.IntSlice
values [][]int
}
func (h hp) Less(i, j int) bool {
a, b := h.values[h.IntSlice[i]], h.values[h.IntSlice[j]]
return a[len(a)-1] < b[len(b)-1]
}
func (hp) Push(any) {}
func (h *hp) Pop() (_ any) { a := h.IntSlice; h.IntSlice = a[:len(a)-1]; return }
// 排序
func maxSpending2(values [][]int) int64 {
m, n := len(values), len(values[0])
a := make([]int, 0, m*n)
for _, row := range values {
a = append(a, row...)
}
slices.Sort(a)
ans := 0
for i, x := range a {
ans += x * (i + 1)
}
return int64(ans)
}
cpp 解法, 执行用时: 196 ms, 内存消耗: 54.2 MB, 提交时间: 2023-11-13 20:48:58
class Solution {
public:
long long maxSpending(vector<vector<int>> &values) {
int m = values.size(), n = values[0].size();
vector<int> a;
a.reserve(m * n);
for (auto &row: values) {
a.insert(a.end(), row.begin(), row.end());
}
sort(a.begin(), a.end());
long long ans = 0;
for (int i = 0; i < a.size(); i++) {
ans += (long long) a[i] * (i + 1);
}
return ans;
}
long long maxSpending2(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].back(), i);
}
long long ans = 0;
for (int d = 1; d <= m * n; d++) {
auto [v, i] = pq.top();
pq.pop();
ans += (long long) v * d;
values[i].pop_back();
if (!values[i].empty()) {
pq.push({values[i].back(), i});
}
}
return ans;
}
};
java 解法, 执行用时: 41 ms, 内存消耗: 55.7 MB, 提交时间: 2023-11-13 20:48:31
class Solution {
public long maxSpending(int[][] values) {
int m = values.length, n = values[0].length;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> values[a[0]][a[1]] - values[b[0]][b[1]]);
for (int i = 0; i < m; i++) {
pq.offer(new int[]{i, n - 1});
}
long ans = 0;
for (int d = 1; d <= m * n; d++) {
int[] p = pq.poll();
int i = p[0], j = p[1];
ans += (long) values[i][j] * d;
if (j > 0) {
pq.offer(new int[]{i, j - 1});
}
}
return ans;
}
public long maxSpending2(int[][] values) {
int m = values.length, n = values[0].length;
int[] a = new int[m * n];
int i = 0;
for (int[] row : values) {
System.arraycopy(row, 0, a, i, n);
i += n;
}
Arrays.sort(a);
long ans = 0;
for (i = 0; i < a.length; i++) {
ans += (long) a[i] * (i + 1);
}
return ans;
}
}
python3 解法, 执行用时: 144 ms, 内存消耗: 30.2 MB, 提交时间: 2023-11-13 20:48:08
class Solution:
# 排序
def maxSpending(self, values: List[List[int]]) -> int:
a = sorted(x for row in values for x in row)
return sum(x * i for i, x in enumerate(a, 1))
# 最小堆
def maxSpending2(self, values: List[List[int]]) -> int:
h = [(a[-1], i) for i, a in enumerate(values)]
heapify(h)
ans = 0
for d in range(1, len(values) * len(values[0]) + 1):
v, i = heappop(h)
ans += v * d
values[i].pop()
if values[i]:
heappush(h, (values[i][-1], i))
return ans