【LeetCode每日一题】受标签影响的最大值【中等】

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

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

子集 s 的大小 小于或等于 numWanted 。

s 中 最多 有相同标签的 useLimit 项。

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

返回子集 s 的最大 分数 。

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1

输出：9

解释：选出的子集是第一项，第三项和第五项。

示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2

输出：12

解释：选出的子集是第一项，第二项和第三项。

示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1

输出：16

解释：选出的子集是第一项和第四项。

提示：

n == values.length == labels.length

1 <= n <= 2 * 104

0 <= values[i], labels[i] <= 2 * 104

1 <= numWanted, useLimit <= n

题解：

这道题的思路还是很容易想到的，可以采用贪心的思想，首先将数组进行排序，因为仅仅是要求同类型的数字数量不超过uselimit，所以可以在同类型的数字中优先拿大的数字。当同类型的数字拿够数量了，就跳过，拿其他标签的。

可以使用map作标记，标记已经拿取的同标签数字的数量。

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        int n = values.size();
        vector<pair<int, int>> p;
		//将值和标签绑定
        for(int i = 0; i < n; i++){
            p.push_back(make_pair(values[i], labels[i]));
        }
		//排序
        sort(p.begin(), p.end());
        map<int, int> m;
        int sum = 0;
        int cnt = 0;
		//从大到小取数字，加到sum中
        for(int i = n - 1; i >= 0; i--){
            int label = p[i].second;
			//如果满足题目条件，就选取
            if(m[label] < useLimit && cnt < numWanted){
                sum += p[i].first;
                m[label]++;
                cnt++;
            }
        }
        return sum;
    }
};