Educational Codeforces Round 114 (Rated for Div. 2)D. The Strongest Build 优先队列

Educational Codeforces Round 114 (Rated for Div. 2)D. The Strongest Build 优先队列

题目链接

题目大意

有n个序列 每个序列可以选一个数 每个数的和为ans

给你m个选择方式 你的最终答案不能包含这m种选择

问你最大的答案ans

维护第k大的思想

题目思路

用优先队列先将最大的那种可能放进去队列里 注意node包含sum和vec选择方式 针对sum从大到小排序

如果当前选择方式没有在这m种方式里面 则输出答案

否则对于当前选择方式的每一个序列选的数进行减小一个 重新计算sum和vec填入优先队列中

题目代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int t,n,m,k;
vector<int >g[15],v,now;//g是初始序列 
map<vector<int >,bool>mp,use;//用于判断是否不让用该序列 
struct node{int v;vector<int >vec;bool operator <(const node &x)const{return v<x.v;}
}n1;
priority_queue<node >q;
int main()
{cin>>n;int sum=0;for(int i=1;i<=n;i++){int x;cin>>x;for(int j=1;j<=x;j++){cin>>t;g[i].push_back(t);}now.push_back(x-1);sum+=g[i][x-1];} cin>>m;for(int i=1;i<=m;i++){v.clear();for(int j=1;j<=n;j++){cin>>t;v.push_back(t-1);}mp[v]=1;}q.push(node{sum,now});while(!q.empty()){n1&#p();q.pop();now=n1.vec;if(use[now])continue;use[now]=1;sum=n1.v;if(mp[now]!=1){for(int i=0;i<now.size();i++)cout<<now[i]+1<<" ";cout<<endl;break;}int sum2=sum;for(int i=1;i<=n;i++){if(now[i-1]<1)continue;sum2-=g[i][now[i-1]];now[i-1]--;sum2+=g[i][now[i-1]];if(use[now]==0){q.push(node{sum2,now});}now[i-1]++;sum2=sum;}}return 0;
}