题解：P16830 【MX-X29-T1】『FeOI-6』基站建设 2

· · 题解

签个到就跑了。

显然可以把两个序列的点都去重了。

把第一个序列的点视作基准点，于是题意转化成选定若干个区间使得所有点都被包含的同时每个区间都含有至少一个基准点。

考虑先把每个点都视作一个独立的区间，然后通过覆盖两个区间中间的点的方式合并区间。

每次合并的代价是这右区间左端点到左区间右端点的距离。

这个东西看起来就很像最小生成树不是吗！

我们先把所有的基准点设置为连通，然后每个点向左右两个最近的点连一个边，跑最小生成树即可。

值域很大要离散化，时间复杂度 O(n\log n)。

代码是一边阴暗扭动一边写出来的，可能很糖。

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int op=114;
int vis[N],fa[N];
int find(int x){
    if(vis[x]==op)return fa[x]==x?x:fa[x]=find(fa[x]);
    vis[x]=op,fa[x]=x;
    return x;
}
int a[N];
int b[N];
int mp[N];
struct fish{
    int u,v,w;
};
bool cmp(fish x,fish y){
    return x.w<y.w;
}
void solve(){
    op++;
    int n,m;
    cin>>n>>m;
    set<int>A;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        A.insert(x);
    }
    n=0;
    for(int i:A)
    a[++n]=i;
    A.clear();
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        A.insert(x);
    }
    m=0;
    for(int i:A)
    b[++m]=i;
    vector<int>lsh;
    for(int i=1;i<=n;i++)
    lsh.push_back(a[i]);
    for(int i=1;i<=m;i++)
    lsh.push_back(b[i]);
    sort(lsh.begin(),lsh.end());
    for(int i=1;i<=n;i++){
        int x=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
        mp[x]=a[i];
        a[i]=x;
    }
    for(int i=1;i<=m;i++){
        int x=lower_bound(lsh.begin(),lsh.end(),b[i])-lsh.begin()+1;
        mp[x]=b[i];
        b[i]=x;
    }
    vector<fish>ve;
    for(int i=1;i<lsh.size();i++)
    ve.push_back({i,i+1,lsh[i]-lsh[i-1]});
    for(int i=1;i<=n;i++)
    fa[find(a[i])]=find(0);
    sort(ve.begin(),ve.end(),cmp);
    int ans=0;
    for(fish i:ve)
    if(find(i.u)!=find(i.v)){
        ans+=i.w;
        fa[find(i.u)]=find(i.v);
    }
    cout<<ans<<'\n';
}
int main(){
    int c,t;
    cin>>c>>t;
    while(t--)solve();
    return 0;
}
//「对不起对不起！」
// 菈琪旭点头如捣蒜，飞快地代替毫不愧疚的可蓉赔罪。

//「呃，可蓉从以前就是这样子，她完全没有恶意，只是对于跟自己变得要好的人，她就会做出那样的事情，她并不是坏孩子，我是说真的，其实她真的是个好孩子。」

//「我明白啦，不要紧不要紧。」
// 只要可蓉有一丝丝恶意或杀气，这条手臂大概早就断了。

//「这……这样啊。太好了。」