自动搬运

查看原文

来自洛谷，原作者为

	bloodstalk 正难则反，宁慢勿粗

搬运于2025-08-24 22:40:25，当前版本为作者最后更新于2022-10-16 15:28:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

update：修改了一下 $\LaTeX$

很好的一个题

题意

给你 $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)$ ,可以通过。

自认为写的很详细了，有什么问题可以在评论区问。