CF1056C Pick Heroes 题解

· · 题解

CF1056C Pick Heroes 题解

题解同步发表于 CSDN~

引入：

洛谷题解中要么代码没放，要么代码很长很繁琐。因此我来交一发代码量只有 1008 B 的题解。

算法：贪心

考虑这种博弈题常用的思考方式：分类讨论先后手。

先手：

注意到题目中说每对仇敌必须一起选。因为我们要保留先手的优势，所以我们应当先选择每对英雄中战斗力最强的。

之后，再选择剩余英雄中战斗力最强的即可。

后手：

如果交互库选择了仇敌中的一个，那么只能选与之相匹配的英雄。

否则，我们就获得了先手，之后便和先手策略一致了。

数据结构：

因为我们要维护战斗力最强的英雄，所以可以用 set 或者 priority_queue。这里我选择了 set，因为 set 可以很方便地删除其中的任意元素。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e3+10;
ll n,m,op,t,c,a[N],b[N],p[N],l[N],x[N];
bool vis[N];
multiset<pair<ll,ll> > q; 
void first(){
    for(int i=1;i<=m;i++)
        if(!vis[i]){
            cout<<(p[a[i]]>p[b[i]]?a[i]:b[i])<<"\n";
            fflush(stdout); 
            cin>>t;
            q.erase({-p[a[i]],a[i]});
            q.erase({-p[b[i]],b[i]});
        }   
    while(!q.empty()){
        cout<<(*q.begin()).second<<"\n";
        q.erase(q.begin());
        fflush(stdout); 
        if(!q.empty()){cin>>t;q.erase({-p[t],t});}      
    }
}
int main(){
    cin>>n>>m;c=m;
    for(int i=1;i<=n*2;i++) cin>>p[i],q.insert({-p[i],i});
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i],l[a[i]]=b[i],l[b[i]]=a[i],x[a[i]]=x[b[i]]=i;
    cin>>op;
    if(op==1) first();
    else
        for(int i=1;i<=n;i++){
            cin>>t;
            q.erase({-p[t],t});
            if(l[t]&&q.find({-p[l[t]],l[t]})!=q.end()){
                cout<<l[t]<<"\n";
                fflush(stdout); 
                q.erase({-p[l[t]],l[t]});vis[x[t]]=1;
            }else{first();break;}
        }
    return 0;
}

代码很短，只有 41 行。

怎么样？点个赞再走吧~