很好的一个题
题意
给你 \(n\) 个三元组 \((r_1,r_2,r_3)\) , 并定义 \(ρ = \lfloor \frac{1}{4}min(r_1,r_2,r_3)^3 \rfloor\) 。
两个三元组能合并当且仅当这两个三元组有至少两个值相同，即从 \((x_1,y,z)\) 和 \((x_2,y,z)\) 变为 \((x_1+x_2,y,z)\) 。\((x,y,z)\)的位置不固定，可以变为 \((x,z,y)\) 等很多种。一个三元组最多只能合并一次。
询问 $ ρ $ 最大为多少，并且询问是合并后形成的还是不合并形成的，再询问他们的编号。
\(1 \leq n \leq 5 \times 10^5\)
，$1 \leq r_{i,1},r_{i,2},r_{i,3} \leq 10^3 $
。
思路
贪心
-
首先，我们可以知道， \(ρ\) 的值只跟三元组中最小的一个数有关。
因此，如果我们要合并， \(x_1,x_2\) 却不是他们所在的三元组中最小的那一个数，那么他们合并也毫无意义，因为最后还是看最小的那一个数。所以我们先给每个三元组自身从小到大排一下序。
-
再者，有了这个条件后，我们想一想：
1.如果有多组\((\geq 2)\)三元组的后两个元素相等，那么可以很轻松的想出，合并肯定是比不合并优的。
2.如果有多组三元组的后两个元素相等，我们应贪心的选取最大的两个 \(x\) 值进行合并，因此，我们只需要维护最大的两个值就可以了。
-
有了基本思路后我们看一看数据范围 ：$1 \leq r_{i,1},r_{i,2},r_{i,3} \leq 10^3 $ ，完全可以进行 \(O(r^2)\) 枚举！
因此，思路就出来了：\(mp[i][j][1],mp[i][j][2]\) 表示三元组后两个元素分别是 \(i,j\) 时，第一个元素的最大值和次大值，我们只需要对这两个值进行维护即可。 \(cnt[i][j]\) 存储后两个元素分别是 \(i,j\) 时一共有多少个三元组，\(id[i][j]\) 则存储它们的编号。
特殊地，如果我们最后枚举的时候进行合并 ，\(x_1+x_2\) 的值加起来要大于 \(i\) , 那么最小值就是 \(i\) 而不是 \(i+j\) ，不要漏掉这种情况。
不懂的看一看代码理解一下吧。
代码实现
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e3 + 5;
const int M = 5e5 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
int mp[N][N][3],cnt[N][N],id[N][N][3];
struct node{
int x,y,z,id;
}a[M];
int n,s1,s2;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il bool mysort(node a,node b) { return a.x > b.x; }
signed main()
{
n = read();
int ans = 0 , op = 0;
for(re int i=1;i<=n;i++)
{
a[i].id = i;
a[i].x = read() , a[i].y = read() , a[i].z = read();
if(a[i].x > a[i].y) swap(a[i].x,a[i].y);
if(a[i].x > a[i].z) swap(a[i].x,a[i].z);
if(a[i].y > a[i].z) swap(a[i].y,a[i].z);/*给三元组排序*/
int x = a[i].x , y = a[i].y , z = a[i].z;/*如果 cnt[i][j] 存储的还不到2，直接加入进去就行*/
if(cnt[y][z] == 0 || cnt[y][z] == 1) mp[y][z][++cnt[y][z]] = x , id[y][z][cnt[y][z]] = i;
else
{/*cnt[i][j]为2了，我们就需要维护最大值和次大值*/
if(mp[y][z][1] > mp[y][z][2]) swap(mp[y][z][1],mp[y][z][2]) , swap(id[y][z][1],id[y][z][2]);/*把小的交换到前面*/
if(x > mp[y][z][1]) mp[y][z][1] = x , id[y][z][1] = i;
}
}
//cout << mp[963][991][1] << " " << mp[963][991][2] << endl;
for(re int i=1;i<=1000;i++)
for(re int j=i;j<=1000;j++)
{
if(cnt[i][j] == 0) continue;
if(cnt[i][j] == 1)/*只有一个元素，直接判断就行*/
{
if(ans < mp[i][j][1]) ans = mp[i][j][1] , op = 0 , s1 = id[i][j][1];
}
if(cnt[i][j] == 2)
{
if(mp[i][j][1] + mp[i][j][2] > i) /*特殊情况，最小值是i而不是x1+x2的时候*/
{
if(ans < i) ans = i , op = 1 , s1 = id[i][j][1] , s2 = id[i][j][2];
}
else
{
if(ans < mp[i][j][1] + mp[i][j][2]) ans = mp[i][j][1]+mp[i][j][2] , op = 1 , s1 = id[i][j][1] , s2 = id[i][j][2];
}
}
}
if(op == 0) cout << op << "\n" << s1 << "\n" << (ans*ans*ans)/4;
else cout << op << "\n" << min(s1,s2) << " " << max(s1,s2) << "\n" << (ans*ans*ans)/4;/*愉快的输出*/
/*cout << a[288].x << " " << a[288].y << " " << a[288].z << endl;
cout << a[727].x << " " << a[727].y << " " << a[727].z;*/
return 0;
}
时间复杂度 \(\Theta(r^2)\) ,可以通过。
自认为写的很详细了，有什么问题可以在评论区问。