P8957题解

· · 题解

贪心思路，简洁明了。

题目分析

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

我们考虑一个点一个点的加入进来，这样肯定会和之前某个点产生连接，最简单的贪心思路就是使这条新产生的连边尽可能小就可以了。由于加入点的顺序并不会产生影响，我们不妨按数列 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;
}