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

简介: 【 贪心 临项交换 多指针】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 <= 104

1 <= values[i][j] <= 106

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++**实现。

相关文章
定义函数,并用指针交换两个变量内容(正确版和错误版+错误原因)
定义函数,并用指针交换两个变量内容(正确版和错误版+错误原因)
96 0
定义函数,并用指针交换两个变量内容(正确版和错误版+错误原因)
|
存储 C语言
【C 语言】二级指针作为输入 ( 自定义二级指针内存 | 二级指针排序 | 通过 交换指针指向的内存数据 方式进行排序 )
【C 语言】二级指针作为输入 ( 自定义二级指针内存 | 二级指针排序 | 通过 交换指针指向的内存数据 方式进行排序 )
120 0
【C 语言】二级指针作为输入 ( 自定义二级指针内存 | 二级指针排序 | 通过 交换指针指向的内存数据 方式进行排序 )
|
存储 C语言
【C 语言】二级指针作为输入 ( 自定义二级指针内存 | 二级指针 排序 | 通过 交换指针方式 进行排序 )
【C 语言】二级指针作为输入 ( 自定义二级指针内存 | 二级指针 排序 | 通过 交换指针方式 进行排序 )
130 0
【C 语言】二级指针作为输入 ( 自定义二级指针内存 | 二级指针 排序 | 通过 交换指针方式 进行排序 )
指针(三个数的交换)
#include swap(int *p1, int *p2){ int temp; temp = *p1; *p1 = *p2; *p2 = temp; } exchange(int *ep1, int *ep2, ...
611 0
|
2月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
29 0
|
3月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
|
4月前
|
C语言
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)