D. The Strongest Build
tilian
发现n只有10啊 m也是1e5
我们考虑最好的状态肯定就是大家都选最大的时候
但是如果被禁用掉了的话咋办呢
我们肯定贪心的去减少一个最小的地方
但是要是有很多地方减少的一样 那就难办了
但是我们可以直接暴力 因为m只有10 我们每次都会排除一个答案
最坏也就是搞出m个check
我们直接用大根堆 每次bfs更新一下可以去往的状态 以及 他们的权值
最后注意一些剪枝即可 比如已经搞过的状态就可以不搞了
复杂度mlognm
int a[10][N],n,m;
void solve(){
cin>>n;
vector<int>ans(n);
for(int i=0;i<n;i++){
int x;cin>>x;
ans[i]=x-1;
for(int j=0;j<x;j++){
cin>>a[i][j];
}
}
set<vector<int>>s;
cin>>m;
int sum=0;
for(int i=0;i<m;i++){
vector<int>v;
for(int j=0;j<n;j++){
int x;cin>>x;
v.push_back(x-1);
}
sum+=v.back();
s.insert(v);
}
priority_queue<pair<int,vector<int>>>pq;
pq.push({sum,ans});
set<vector<int>>S;
while(pq.size()){
auto [w,v]=pq.top();
pq.pop();
if(S.count(v))continue;
else S.insert(v);
if(!s.count(v)){
for(auto i:v)cout<<i+1<<' ';
return;
}
for(int i=0;i<n;i++){
if(!v[i])continue;
v[i]--;
pq.push({w-a[i][v[i]+1]+a[i][v[i]],v});
v[i]++;
}
}
}
标签:10,Educational,pq,int,auto,sum,Codeforces,114
From: https://www.cnblogs.com/ycllz/p/17020904.html