题解：P9525 [JOISC2022] 团队竞技

· · 题解

题解：P9525 [JOISC2022] 团队竞技

思路

我们这题直接贪心即可 。

首先我们写一个结构体，一个存能力值（不管它是哪个），一个存位置，然后写一个重载运算符，维护优先队列中取出的为结构体的值最大 。

然后我们就将三个能力值分别丢进三个优先队列里面，记得把下表也丢进去 。

循环的时候只要三个优先队列里面都有值，就可以继续，否则停止 。

我们分别取出三个队列的顶部结构体，如果这种能力已经出现过了，直接将这个顶部删除，然后循环下一个 。

对于其他的不可行情况，就是这个能力的值已经有别的海狸有过了，那么，我们也把这个顶部删除，循环下一个 。

如果所有的不可行情况都通过了，也就是当前方案可行，直接输出三个顶部的和，然后退出程序 。

对于无解情况，一定没有退出过程序，那么，我们在循环外面再输出 -1 。

Code:

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