[プログラマー]ベストアルバム

問題の説明

アイデア

コード#コード#

#include <string>
#include <vector>
#include<unordered_map>
#include<queue>
#include<algorithm>
using namespace std;

struct song{
    int p, i;//identifier
    song(int pp, int ii){
        p = pp;i =ii;
    }
};

struct comp{
    bool operator()(song a, song b){
        if(a.p==b.p){
            return a.i>b.i;
        }
        return a.p<b.p;
    }
};

bool compare(pair<int,priority_queue<song, vector<song>,comp>> &a, pair<int,priority_queue<song, vector<song>,comp>> &b){
    return a.first>b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string,pair<int,priority_queue<song, vector<song>,comp>>> m;
    for(int i = 0;i<genres.size();i++){
        unordered_map<string,pair<int,priority_queue<song, vector<song>,comp>>>::iterator it =
             m.find(genres[i]);
        if(it==m.end()){
            priority_queue<song, vector<song>,comp> pq;
            pq.push(song(plays[i],i));
            m[genres[i]]={plays[i],pq};
        }
        else{
            it->second.second.push(song(plays[i],i));
            it->second.first+=plays[i];
        }
    }
    vector<pair<int,priority_queue<song, vector<song>,comp>>> v;
    for(unordered_map<string,pair<int,priority_queue<song, vector<song>,comp>>>
        ::iterator it = m.begin();it!=m.end();it++){
        v.push_back(it->second);
    }
    sort(v.begin(),v.end(),compare);
    for(int i = 0;i<v.size();i++){
        int ctr = 0;
        
        while(!v[i].second.empty()&&ctr<2){
            answer.push_back(v[i].second.top().i);
            v[i].second.pop();
            ctr++;
        }
    }
    return answer;
}