题解：AT_abc414_d [ABC414D] Transmission Mission

naturelyf · 2025-07-13 08:06:27 · 题解

题目大意

给定 n 个房子和 m 个基站，基站覆盖范围是给基站花的钱向左右延申的一半，基站可以在任意位置，房子只能在整数点上，求最少花费多少钱。

简要思路

发现每多一个基站可以将所有房子划分为两个块，每个基站一个块。这里有一个显然贪心是一个块的最小花费就是块里最后一个的位置减第一个的位置。

由于每多一个基站可以多分一块，又有前面那个贪心，所以显然我们可以将点去重之后将所有点的差分排序，其中分块的点就是差分最大的 m-1 个点。

由于 n\le m 我懒得写，所以直接特判了，下面是赛时代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,m;
int ans;
int a[N];
pair<int,int> diff[N];
vector<int>nd; 
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    if(m>=n){
        cout<<0;
        return 0;
    }
//  if(m==1){
//      cout<<a[n]-a[1];
//      return 0;
//  }
    for(int i=1;i<n;i++)
        diff[i].first=a[i+1]-a[i],diff[i].second=i;
    sort(diff+1,diff+n);
    int p=n-1;
//  for(int i=1;i<=p;i++)cout<<cf[i].second<<' ';
    for(int i=1;i<m;i++)nd.push_back(diff[p-i+1].second);
    sort(nd.begin(),nd.end());
    nd.push_back(n);
    int lst=1;
    for(int i:nd){
//      cout<<i<<' ';
        ans+=a[i]-a[lst];
        lst=i+1;
    }
    cout<<ans;
    return 0;
}

其中 diff 为差分，nd 为分块的位置，代码应该比较简洁。

建议评黄。