2023-05-23每日一题

一、题目编号

1090. 受标签影响的最大值

二、题目链接

点击跳转到题目位置

三、题目描述

我们有一个 n 项的集合。给出两个整数数组 values 和 labels ，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。

从 n 个元素中选择一个子集 s :

• 子集 s 的大小 小于或等于 numWanted 。
• s 中 最多 有相同标签的 useLimit 项。

一个子集的 分数 是该子集的值之和。

返回子集 s 的最大 分数 。

四、解题代码

class Solution {
public:
struct Good{int value;int label;Good(int value, int label) : value(value), label(label){};
};int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {unordered_map<int, int> hash;int n = values.size();vector<Good> good;for(int i = 0; i < n; ++i){good.push_back(Good(values[i], labels[i]));}  sort(good.begin(), good.end(),[&](Good &a, Good &b){return a.value > b.value;});int num = 0;int res = 0;for(int i = 0; i < n; ++i){if(useLimit == hash[good[i].label]){continue;}num++;hash[good[i].label]++;res += good[i].value;if(num == numWanted){break;}}return res;}
};

五、解题思路

(1) 首先使用结构体将values和labels两个数组中的信息合并到一起，合并到good数组中。

(2) 将good数组按照价值从大到小来进行排序。（使用C++的自定义排序）。

(3) 继续遍历good数组，用哈希表来统计取得相同标签的项，如果取得相同标签的项已经等于限制就不取，直到取到所能取的物品的上限或者遍历完数组为止。

(4) 返回累加的结果即可。