【 贪心 临项交换 多指针】2931. 购买物品的最大开销

本文涉及知识点

排序 多指针 贪心 临项交换

LeetCode2931. 购买物品的最大开销

给你一个下标从 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 <= 10

1 <= n == values[i].length <= 10⁴

1 <= values[i][j] <= 10⁶

values[i] 按照非递增顺序排序。

排序

要想开销最大，先买价值小的。下面来证明：

v1 < v2 ，t1 < t2。 t1购买v2,t2购买v1。则两项的价值为：

t1v2+t2v1，令t2=t1+t3，则t1v2+t1v1+t3v1。

假定t1购买v1，t2购买v2，则两项的价值：

t1v1 + t1v2+t3v2

两者相减：

t3v1-t3v2 = t3(v1-v2) 为负，故旧方案劣于新方案。

将数据放到有序映射中

时间复杂度😮(mnlog(mn))。

代码

class Solution {
public:
  long long maxSpending(vector<vector<int>>& values) {
    multiset<int> setNum;
    for (const auto& v : values) {
      setNum.insert(v.begin(), v.end());
    }
    int d = 1;
    long long llRet = 0;
    for (const auto& n : setNum) {
      llRet += (long long)n * d++;
    }
    return llRet;
  }
};

行已经排序

只对各行的尾元素排序，key 尾元素的大小，value 行索引。注意： 键可能重复。

时间复杂度稍稍下降，为：O(nmlogn)。

代码

class Solution {
public:
  long long maxSpending(vector<vector<int>>& values) {
    std::priority_queue<pair<int, int>,vector<pair<int, int>>,greater<>> minHeapNumRow;
    for (int i = 0; i < values.size();i++) {
      minHeapNumRow.emplace(values[i].back(), i);
      values[i].pop_back();
    }
    int d = 1;
    long long llRet = 0;
    while(minHeapNumRow.size()){
      auto[n,r] = minHeapNumRow.top();
      minHeapNumRow.pop();
      llRet += (long long)n * d++;
      if (values[r].size()) {
        minHeapNumRow.emplace(values[r].back(), r);
        values[r].pop_back();
      }
    }
    return llRet;
  }
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。