[C++知识库]codeforces - 1574D - The Strongest Build

题目连接：Problem - 1574D - Codeforces

题目大意：

1个玩家有n个装备槽，第i个装备槽中有c[i]个装备，这c[i]个装备中第j个武器的武力值为a[i][j]。玩家每次从每个装备槽中选择一个装备，构成一个装备组合。

游戏给玩家设定m种被ban的装备组合，程序需要输出没有被ban的组合中玩家可以选出的武力总值最高的一个装备组合。

题解：

将每一条被ban的组合插入set ss中。

用pair<int, vector<int>>记录每一种组合的<strength，build index>，将pair插入优先队列中，优先队列中的元素按照strength值降序排序（大顶堆）。每一次插入元素，同时将插入过优先队列的组合记录在set sq中。

首先将组合（c1,c2,...,cn）（即strength最大的组合）加入优先队列中。

循环查看优先队列顶部的组合是否被ban（即是否在set ss中）：

若被ban，则弹出该组合，并将strength总值次之的（c1-1,c2,...,cn），（c1,c2-1,...,cn），（c1,c2,...,cn-1）中没有加入过优先队列的组合（即该组合不在set sq中）依次加入。

直到优先队列顶部的组合不在被ban的set中停止循环，答案即为此时优先队列顶部的组合。

#include "bits/stdc++.h"
using namespace std;
 
 
int main(){
    int n,m;
    scanf("%d", &n);
    int c[n];
    int a[n][200001];
    priority_queue<pair<int,vector<int>>> q;
    set<vector<int>> ss;
    set<vector<int>> sq;
    for(int i = 0 ; i < n ; i++){
        scanf("%d", &c[i]);
        for(int j = 0 ; j < c[i] ; j++){
            scanf("%d", &a[i][j]);
        }
    }
    scanf("%d", &m);
    if(m == 0){
        for(int i = 0 ; i < n ; i++){
            printf("%d ", c[i]);
        }
        return 0;
    }
    
    int b[m][n];
    for(int i = 0 ; i < m ; i++){
		vector<int> v;
        for(int j = 0 ; j < n ; j++){
            scanf("%d", &b[i][j]);
            v.push_back(b[i][j]);
        }
        ss.insert(v);
    }
    
    vector<int> vc;
    for(int i = 0 ; i < n ; i++){
        vc.push_back(c[i]);
    }
    
	pair<int,vector<int>> x;
    x.second = vc;
    x.first = 0;
    for(int i = 0 ; i < n ; i++){
        x.first += a[i][vc[i]-1];
    }    
    q.push(x);
    sq.insert(x.second);
    
    while(ss.find(q.top().second) != ss.end()){
        pair<int,vector<int>> eq = q.top();
        q.pop();
        vector<int> tp = eq.second;
        for(int i = 0 ; i < n ; i++){
            if(tp[i] == 1) continue;
            tp[i]--;
            if(sq.find(tp) != sq.end()){
                tp[i]++;
                continue;
            }
            pair<int,vector<int>> k;
            k.second = tp;
			k.first = 0;
            for(int j = 0 ; j < n ; j++){
                k.first += a[j][tp[j]-1];
            } 
            q.push(k);
            sq.insert(k.second);
            tp[i]++;
        }
    }
    
    pair<int,vector<int>> res = q.top();
    for(int i = 0 ; i < n ; i++){
        printf("%d ", res.second[i]);
    }
}