[JOISC2022] 团队竞技

分析

首先这道题本质上离不开一个思想，就是我们贪心地选择最大的 \(a_i+b_j+c_k\) 的 \(i,j,k\)，但是碍于题目的限制，外加观察样例会发现有一些人是永远不可能选择的，例如样例 \(1\) 中的第 \(3\) 人，他的 \(b_i,c_i\) 都是最大的，不管剩余 \(2\) 人如何选，总是不满足题意。

因此，如果某个人的其中 \(2\) 项指标（或以上）是所有人中最大的，那么一定不能选他。使用优先队列维护当前 \(a,b,c\) 里的最大值，如果其中某个数列里的最大值的人，同时也是另一个数列中达到最大值的人，那么他必定不能选。开数组 \(del_i\) 表示 \(i\) 是否是不能选的。如果优先队列里开头的若干个元素都不能选，就 pop() 掉。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N=150010;
#define pii pair<int,int>
int a[N],b[N],c[N],del[N];
priority_queue<pii> x,y,z;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		x.push({a[i],i});
		y.push({b[i],i});
		z.push({c[i],i});
	}
	while(!x.empty()&&!y.empty()&&!z.empty())
	{
		int i=x.top().second,j=y.top().second,k=z.top().second;
		del[i]|=(b[i]==b[j])|(c[i]==c[k]);
		del[j]|=(a[i]==a[j])|(c[j]==c[k]);
		del[k]|=(a[i]==a[k])|(b[j]==b[k]);
		if(!(del[i]+del[j]+del[k]))//都能选
		{
			cout<<a[i]+b[j]+c[k];
			return 0;
		}
		while(!x.empty()&&del[x.top().second]) x.pop();
		while(!y.empty()&&del[y.top().second]) y.pop();
		while(!z.empty()&&del[z.top().second]) z.pop();
	}
	cout<<-1;
}