CF1056C Pick Heroes 题解

· · 题解

思路

分两种情况讨论：

先手：

显然，通过选一对仇敌关系之中的一个，可以确定让交互库选另一个。所以，先选所有仇敌关系中 p_i 较大的一方，是最优策略；仇敌关系处理完之后，只需依次选没选过的 p_i 中的最大值，而交互库就只能选次大，以此类推。

策略：先选所有仇敌关系中 p_i 较大的一方，选完后每次选剩余 p_i 中最大的，知道选完为止。

后手：

如果交互库选了仇敌关系中的一员，那么只能选这个仇敌关系中的另一个；如果交互库没有那么做，那主动权就落到了我们手里：相当于我们是先手。那么只要和先手一样继续做就行了。

策略：如果交互库选了仇敌关系中的一个，则选另一个；否则：先选剩余仇敌关系中 p_i 较大的一方，选完后每次选剩余 p_i 中最大的，知道选完为止。

本题数据范围较小，如果要找没有选的最大的 p_i 或没有选的仇敌关系，直接遍历即可，时间复杂度 O(n^2)。同样，可以用 map 等 STL 或一些数据结构维护，是时间复杂度达到 O(n\log n)。

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl endl<<endl
using namespace std;
int n,m,t,p[2005];
pair<int,int> dis[1005];
bool cho[2005];
struct node{
    int num,idx;
    node(){}
    node(int _num,int _idx){
        num=_num;
        idx=_idx;
    }
    friend bool operator < (node a,node b){
        if(a.num!=b.num) return a.num<b.num;
        return a.idx<b.idx;
    }
};
int fnd(int x){
    for(int i=1;i<=m;i++){
        if((dis[i].fi==x&&!cho[dis[i].se])
         ||(dis[i].se==x&&!cho[dis[i].fi])) return i;
    }
    return 0;
}//找第一个没有选的
//其实可以用map维护，但是容易写挂（我很懒的
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n*2;i++) cin>>p[i];
    for(int i=1;i<=m;i++) cin>>dis[i].fi>>dis[i].se;
    cin>>t;
    priority_queue<node> q;
    for(int i=1;i<=n*2;i++){
        q.push(node(p[i],i));
    }
    if(t==1){//先手
        for(int i=1;i<=m;i++){
            if(p[dis[i].fi]<p[dis[i].se]) swap(dis[i].fi,dis[i].se);
            cout<<dis[i].fi<<endl;
            int x;
            cin>>x;
            cho[x]=cho[dis[i].fi]=true;
            //优先使用仇敌关系
        }
        while(!q.empty()){
            while(!q.empty()&&cho[q.top().idx]) q.pop();
            if(q.empty()) break;
            cout<<q.top().idx<<endl;
            cho[q.top().idx]=true;
            int x;
            cin>>x;
            cho[x]=true;
        }//找最大
    }
    if(t==2){
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            cho[x]=true;
            int tmp=fnd(x);
            if(tmp){
                if(dis[tmp].fi==x){
                    cho[dis[tmp].se]=true;
                    cout<<dis[tmp].se<<endl;
                }
                else{
                    cho[dis[tmp].fi]=true;
                    cout<<dis[tmp].fi<<endl;
                }
                //如果是仇敌关系中的一员
            }
            else{
                bool chod=false;
                for(int i=1;i<=m;i++){
                    if(!cho[dis[i].fi]&&!cho[dis[i].se]){
                        chod=true;
                        if(p[dis[i].fi]<p[dis[i].se]) swap(dis[i].fi,dis[i].se);
                        cout<<dis[i].fi<<endl;
                        cho[dis[i].fi]=true;
                        break;
                        //如果还有仇敌关系
                    }
                }
                if(!chod){
                    while(!q.empty()&&cho[q.top().idx]) q.pop();
                    cout<<q.top().idx<<endl;
                    cho[q.top().idx]=true;
                    //没有了仇敌关系，找最大
                }
            }
        }
    }
    return 0;
}