题解：P9525 [JOISC2022] 团队竞技

Slclcc · 2024-08-05 18:51:12 · 题解

思路

一道贪心题。

我们可以定义一个结构体，存能力值和下标。

并定义三个优先队列，分别存三个的能力值和当前下标。

判断以下两点：

• 是否已经在别的优先队列中将队顶下标的元素弹出，也就是之前该下标的元素判断不合法；
• 该元素所在的下标是否在两个队顶出现，如果是，则代表不是每个成员都有一项能力值严格大于其他两人的对应能力值，将队顶元素弹出。

如果某一次循环中，条件全部避开，也就是全部合法，就输出并结束程序。

如果没有输出，就是不存在符合条件的组队，输出 -1。

注意需要重载运算符，让优先队列中取出的为结构体的值最大。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 150005;
int a[N];
int b[N];
int c[N];
bool vis[N];
int n;

struct node
{
    int val, id;
    bool operator < (const node & x) const
    {
        return val < x.val;
    }
};
priority_queue<node> QA, QB, QC;

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i] >> c[i];
        QA.push({a[i], i});
        QB.push({b[i], i});
        QC.push({c[i], i});
    }
    while (!QA.empty() and !QB.empty() and !QC.empty())
    {
        node A = QA.top();
        node B = QB.top();
        node C = QC.top();
        if (vis[A.id])
        {
            QA.pop();
            continue;
        }
        if (vis[B.id])
        {
            QB.pop();
            continue;
        }
        if (vis[C.id])
        {
            QC.pop();
            continue;
        }
        if (a[B.id] == A.val)
        {
            vis[B.id] = 1;
            QB.pop();
            continue;
        }
        if (a[C.id] == A.val)
        {
            vis[C.id] = 1;
            QC.pop();
            continue;
        }
        if (b[A.id] == B.val)
        {
            vis[A.id] = 1;
            QA.pop();
            continue;
        }
        if (b[C.id] == B.val)
        {
            vis[C.id] = 1;
            QC.pop();
            continue;
        }
        if (c[B.id] == C.val)
        {
            vis[B.id] = 1;
            QB.pop();
            continue;
        }
        if (c[A.id] == C.val)
        {
            vis[A.id] = 1;
            QA.pop();
            continue;
        }
        cout << A.val + B.val + C.val << endl;
        return 0;
    }
    cout << -1 << endl;
    return 0;
}