LeetCode1090.受标签影响的最大值（优先队列）Michael是个半路程序员-

1. 题目

我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。

我们从这些项中选出一个子集 S，这样一来：

• |S| <= num_wanted
• 对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。

返回子集 S 的最大可能的 和。

示例 1： 输入：values = [5,4,3,2,1], labels = [1,1,2,2,3],  num_wanted = 3, use_limit = 1 输出：9 解释：选出的子集是第一项，第三项和第五项。  示例 2： 输入：values = [5,4,3,2,1], labels = [1,3,3,3,2],  num_wanted = 3, use_limit = 2 输出：12 解释：选出的子集是第一项，第二项和第三项。  示例 3： 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1],  num_wanted = 3, use_limit = 1 输出：16 解释：选出的子集是第一项和第四项。  示例 4： 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1],  num_wanted = 3, use_limit = 2 输出：24 解释：选出的子集是第一项，第二项和第四项。   提示： 1 <= values.length == labels.length <= 20000 0 <= values[i], labels[i] <= 20000 1 <= num_wanted, use_limit <= values.length 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-values-from-labels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 数据按标签分入各自的优先队列中
• 每个优先队列取出前面最大的 use_limit 个到一个大的优先队列 q 中
• 把 q 中的前 num_wanted 个取出来求和就是答案

class Solution { public: int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {      vector<priority_queue<int>> countUse(20001);// for(int i = 0; i < values.size(); ++i)       countUse[labels[i]].push(values[i]); int k, sum = 0;      priority_queue<int> q; for(int i = 0; i <= 20000; ++i) {       k = use_limit; while(k-- && !countUse[i].empty()) {        q.push(countUse[i].top());        countUse[i].pop(); } } while(num_wanted-- && !q.empty()) {       sum += q.top();       q.pop(); } return sum; } }; 

200 ms 77.2 MB