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

· · 题解

求点赞 qwq！

赛时怎么连黄都没切。

思路

为了下面的简洁，称区间 [x,y] 的长度为 y-x。

容易发现我们只用求所有区间的长度之和即可。

我们换个角度看题目：发现我们要给每个 a_i 分配若干个 b_j，要覆盖这些东西的最短区间长度显然就是这些的最大值减最小值。

下面给每个 a_i 分配若干个 b_j，求出覆盖它们的最短区间 [l_i,r_i]。

显然当这些区间不相交的时候是最优的，因为如果区间 [l_{i-1},r_{i-1}] 和 [l_i,r_i] 相交，那么 r_{i-1}\ge l_i，由于都是最短区间，那么两区间端点必存在一个 a_k 或 b_k，显然将值为 r_{i-1} 的 a_k 或 b_k 给到 [l_i,r_i] 区间，或者将值为 l_i 的 a_k 或 b_k 给到 [l_{i-1},r_{i-1}] 更优（或不劣）。

由于区间不相交，题目要求就变成了：将排序后的 b 数组分成 n 段（可以为空），使得 a_i 在第 i 段内。

先给 a 和 b 升序排序，更好处理。

容易发现答案可以变为一个大区间减去这 n 段区间之间的空隙。大区间是 [\min(a_1,b_1),\max(a_n,b_m)]，其中 1\le i\le n,1\le j\le m。

由于又是全部覆盖，所以空隙一定是把所有 a_i 和 b_j 打到数轴上，相邻两个点。

为了使答案最小，那不就是对于所有 1\le i<n，在每个 [a_i,a_{i+1}] 区间中选择两个 b_j,b_{j+1}，使得 b_{j+1}-b_j 最大化作为空隙吗？

然后就没了。

代码

比较容易的实现是把 a 和 b 合在一起，时间复杂度 O((n+m)\log(n+m))。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int c,T,n,m,mx,ans,last;
struct node{int v,id;}x[N];
bool cmp(node x,node y){return x.v<y.v;}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>c>>T;
    while(T--){
        cin>>n>>m,mx=last=0;
        for(int i=1;i<=n;i++)cin>>x[i].v,x[i].id=0;
        for(int i=n+1;i<=n+m;i++)cin>>x[i].v,x[i].id=1;
        sort(x+1,x+n+m+1,cmp),ans=x[n+m].v-x[1].v;
        for(int i=1;i<=n+m;i++){
            if(!x[i].id){
                if(last>0)ans-=mx;
                last=i,mx=0;
            }
            if(i<n+m)mx=max(mx,x[i+1].v-x[i].v);
        }
        cout<<ans<<'\n';
    }
}

但是这样子比较慢，可以换成双指针，时间复杂度 O(n\log n+m\log m)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int c,T,n,m,mx,ans,a[N],b[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>c>>T;
    while(T--){
        cin>>n>>m,mx=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=m;i++)cin>>b[i];
        sort(a+1,a+n+1),sort(b+1,b+m+1),ans=max(a[n],b[m])-min(a[1],b[1]),b[m+1]=1e9;
        for(int i=1,j=1;i<n;i++){//求 [a[i],a[i+1]] 中的空隙 
            while(j<=m&&a[i]>b[j])j++;
            mx=min(a[i+1],b[j])-a[i];
            while(j<=m&&b[j]<=a[i+1])mx=max(mx,min(a[i+1],b[j+1])-b[j]),j++;
            ans-=mx;
        }
        cout<<ans<<'\n';
    }
}

还有一种做法是二分，这里就不多说了，时间复杂度 O((n+m)\log(n+m))。