题解：AT_abc414_d [ABC414D] Transmission Mission

· · 题解

题目描述

在数轴上有 N 栋编号从 1 到 N 的房屋。第 i 栋房屋位于坐标 X_i 。同一坐标上可能有多个房屋。

你需要在数轴上的任意实数坐标位置布置 M 个基站，并为每个基站设置一个非负整数的信号强度。

当某个基站的信号强度设为 x 时，该基站的信号能覆盖到一栋房屋的条件是：基站与该房屋之间的距离不超过 \displaystyle\frac{x}{2} 。特别地，当 x=0 时，只有与该基站同坐标的房屋才能接收到信号。

请设计基站的位置和信号强度，确保每栋房屋至少被一个基站的信号覆盖，并求出信号强度总和的最小可能值。

约束条件

题解

我们翻译一下题面，是将有 n 个点的序列分为 m 个区间来覆盖，要求每个区间的长度之和最小（其它都是迷惑性条件）。

用样例来举例，显然，形成 3 个红色覆盖区间的同时也形成了 2 个蓝色未覆盖区间。

想让 3 个红色区间的长度之和最小，反过来想，就是让 2 个蓝色区间的长度之和最大。

观察蓝色区间的特点，是相邻两点间最长的和次长的距离。相邻两点确保不会有点不被覆盖，最长和次长保证蓝色区间的长度之和最大。

此时就完成题目的转化，找 m-1 个最长的相邻两点的距离。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
const ll N=5e5+9;
ll n,m,ans,a[N];
pair<ll,ll> b[N];
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    ios::sync_with_stdio(0),cout.tie(0);
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    sort(a+1,a+n+1);//别忘了将样例排序
    ans=a[n]-a[1];
    b[1].first=0;b[1].second=0;
    for(int i=2;i<=n;i++){
        b[i].first=a[i]-a[i-1];
        b[i].second=i;
    }
    sort(b+1,b+n+1,[](pair<ll,ll> x,pair<ll,ll> y)->bool{
        return x.first>y.first;
    });
    for(int i=1;i<=m-1;i++){
        ans-=(a[b[i].second]-a[b[i].second-1]);
    }
    cout<<ans<<"\n";
    return 0;
}