自动搬运

查看原文

来自洛谷，原作者为

	MCRS_lizi 神，不惧死亡！

搬运于2025-08-24 22:44:05，当前版本为作者最后更新于2023-01-25 15:08:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

贪心思路，简洁明了。

题目分析

我们都应该学过最小生成树的计算方式，这里就不多讲了。

我们考虑一个点一个点的加入进来，这样肯定会和之前某个点产生连接，最简单的贪心思路就是使这条新产生的连边尽可能小就可以了。由于加入点的顺序并不会产生影响，我们不妨按数列 $a$ 从小到大排序，这样加入第 $i$ 个点时数列 $a$ 产生的贡献一定是 $a_i$，这时只需要考虑数列 $b$ 产生的贡献即可。

其实我们只需要找到已经加入的点之中对应 $b_i$ 最小的那个，与其连边即可。这个直接记录之前的最小值即可。

问题来了，怎么证明这个贪心思路的正确性？

首先我们令数列 $A,B$ 分别为 $a,b$ 从小到大排完序后的结果。

很显然，数列 $a$ 产生的贡献就是 $\sum_{i=2}^n A_i$，并且这个贡献值是对于 $a$ 可以取到的最小贡献。

那么对于数列 $b$，我们每加入一个新的 $b_i$，无非有两种情况：

1. 比数列中最小的大，只会计算一次；
2. 比数列中最小的小，不计算，替代最小的，在之后被计算一次后丢弃。

考虑到 $B_1$ 不可能被计算，贡献依然是 $\sum_{i=2}^n B_i$。

这道题就算是搞定了。

CODE：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
struct edge
{
	int u,v;
}l[1000010];
struct num
{
	int a,b,xh;
}p[1000010],minn;
bool cmp(num u,num v)
{
	return u.a<v.a;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].a;
		p[i].xh=i;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].b;
		p[i].xh=i;
	}
	sort(p+1,p+n+1,cmp);
	minn=p[1];
	for(int i=2;i<=n;i++)
	{
		ans+=p[i].a;
		num u=minn;
		ans+=max(u.b,p[i].b);
		if(p[i].b<minn.b)
		{
		    minn=p[i];
		}
		l[i].u=p[i].xh,l[i].v=u.xh;
	}
	cout<<ans<<"\n";
	for(int i=2;i<=n;i++)
	{
		cout<<l[i].u<<" "<<l[i].v<<"\n";
	}
 	return 0;
}