题解：P9525 [JOISC2022] 团队竞技

_yang_yi_bo_ · 2024-08-12 10:21:35 · 题解

考虑贪心。

这道题的难点在于：每个成员都有一项能力值严格大于其他两人的对应能力值。

首先我们定义一个结构体优先队列，把每种能力值以及所在的下标放入三个不同的优先队列，注意重载运算符时相当于排序中的从小到大排序，也就是定义了一个大根堆。

接着，我们需要判断一下两点：

• 是否已经在别的优先队列中将堆顶下标的元素弹出，也就是之前该下标的元素判断不合法；

• 该元素所在的下标是否在两个堆顶同时出现，若是，则代表不是每个成员都有一项能力值严格大于其他两人的对应能力值，将堆顶元素弹出。

若在某一轮循环判断中，三个堆顶元素全部合法，输出三个堆顶元素的和即可。

#include<bits/stdc++.h>
using namespace std;
struct kkk{
    int val,id;
    bool operator<(const kkk& x)const{
        return val<x.val;
    }
};
priority_queue<kkk> pa,pb,pc;
int n;
int a[150005],b[150005],c[150005];
bool vis[150005];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        pa.push({a[i],i});
        pb.push({b[i],i});
        pc.push({c[i],i});
    }while(!pa.empty()&&!pb.empty()&&!pc.empty()){
        kkk aa=pa.top();
        kkk bb=pb.top();
        kkk cc=pc.top();
        if(vis[aa.id]){
            pa.pop();
            continue;
        }if(vis[bb.id]){
            pb.pop();
            continue;
        }if(vis[cc.id]){
            pc.pop();
            continue;
        }if(a[bb.id]==aa.val){
            vis[bb.id]=1;
            pb.pop();
            continue;
        }if(a[cc.id]==aa.val){
            vis[cc.id]=1;
            pc.pop();
            continue;
        }if(b[aa.id]==bb.val){
            vis[aa.id]=1;
            pa.pop();
            continue;
        }if(b[cc.id]==bb.val){
            vis[cc.id]=1;
            pc.pop();
            continue;
        }if(c[aa.id]==cc.val){
            vis[aa.id]=1;
            pa.pop();
            continue;
        }if(c[bb.id]==cc.val){
            vis[bb.id]=1;
            pb.pop();
            continue;
        }cout<<aa.val+bb.val+cc.val;
        return 0;
    }cout<<-1;
    return 0;
}