Problem
\(\text{Description}\)
给定 \(n\) 个含有三元组 \((x_i ,y_i ,z_i)\)，需要从中选出三个不同的对编号 \(i\)，\(j\)，\(k\)，使得 \(x_i +y_j +z_k\) 最大，并且 \(x_i > \max\{x_j ,x_k\} ,y_j > \max\{y_i ,y_k\} ,z_k > \max\{z_i ,z_j\}\)（我们记作条件 \(A\)），求这个最大值。
\(1\le n\le 1.5\times 10^5\)。
\(\text{Solution}\)
像今年 S T1 一样，我们考虑先把 \(x,y,z\) 这三个属性最大的三元组的编号找出来，然后反悔。
如果这三个编号互不相同，直接输出即可。
否则肯定是某个三元组太强了，被选择了两次。
我们记这个三元组的编号为 \(a\)，假设它在 \(x\)，\(y\) 属性下是最大的。
如果继续选 \(a\)，那么它占据了两个属性的最大值，也就是有至少一个除了 \(a\) 的编号会不满足条件 \(A\)。
那么我们标记不合法即可，后面我们就不选了。
然后考虑贪心，我们每次肯定要去对应属性最大的那个编号，这个用优先队列维护即可。
namespace lolcrying {#define PII pair <int ,int>priority_queue < PII > q0 ,q1 ,q2;signed main(){n = read() ;up(i ,1 ,n){a[i] = read() ,b[i] = read() ,c[i] = read();q0.push({a[i] ,i});q1.push({b[i] ,i});q2.push({c[i] ,i});}while(1) {if(q0.empty() || q1.empty() || q2.empty()) { // 为空就选不下去了，不合法。puts("-1") ; return 0 ;}int x = q0.top().second ,y = q1.top().second ,z = q2.top().second;bool f = 1;if(b[x] == b[y] || c[x] == c[z]) nope[x] = 1 ,f = 0;if(a[x] == a[y] || c[y] == c[z]) nope[y] = 1 ,f = 0;if(a[x] == a[z] || b[y] == b[z]) nope[z] = 1 ,f = 0;// f = 0，表示 x，y，z 中有三元组太【强】了，所以不能成为答案。if(f) {writeln(a[x] + b[y] + c[z]) ;return 0 ;}while(!q0.empty() && nope[q0.top().second]) q0.pop();while(!q1.empty() && nope[q1.top().second]) q1.pop();while(!q2.empty() && nope[q2.top().second]) q2.pop();
// 如果最大值不能选就弹出，注意是 while 不是 if，仔细想一下就知道了。}puts("-1"); // 无解。return 0 ;}}
\(\text{Mistake}\)
-
把
priority < PII >写成priority < PII ,vector < PII > ,greater < PII > >。 -
nope[q0/q1/q2.top().second]写成!nope[q0/q1/q2.top().second]。
\(\text{Reflecting}\)
-
写代码的时候要保持清晰的头脑，算法步骤要在脑子里清晰地呈现。
-
这种题要想到贪心，先啥都不管选最优然后反悔，考场 S T1 10 min 想到 + 写完现在这题想不到，值得深思。