Leetcode 1090. 受标签影响的最大值（DAY 124） ---- 贪心算法学习期（400AC纪念）

原题题目

代码实现（首刷自解TLE 81/81)

class Solution {
    
public:int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
    unordered_map<int,priority_queue<int>> map;unordered_map<int,int> count;int ret = 0;for(int i=0;i<labels.size();++i) map[labels[i]].push(values[i]);while(num_wanted--){
    auto it = map.begin(),tempit = it;if(it == map.end()) break;int tempmax = it->second.top();for(;it!=map.end();++it){
    if(it->second.top() > tempmax) tempit = it;tempmax = max(tempmax,it->second.top());}++count[tempit->first];ret += tempit->second.top();tempit->second.pop();if(tempit->second.empty() || count[tempit->first] == use_limit)   map.erase(tempit);}return ret;}
};

代码实现（首刷自解优化）

class Solution {
    
public:int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
    int ret = 0;vector<pair<int,int>> v;unordered_map<int,int> map;for(int i=0;i<values.size();++i)    v.push_back({
    values[i],labels[i]});sort(v.begin(),v.end(),greater<pair<int,int>>());for(int i=0;i<values.size() && num_wanted;++i){
    if(map[v[i].second] == use_limit)   continue;ret += v[i].first;++map[v[i].second];--num_wanted;}return ret;}
};

400AC纪念