T1 变量

我们首先转化题意：给定一个长度为 $n$ 的数列，将其分为 $k$ 组，最小化各组极差之和。

我们不难想到，如果 $k=1$ 的话，答案就是整个数列的极差，我们对整个数列从小到大排序并计算排序过后的相邻数字间的差值（相邻两数字之间的"间隔"），显然整个数列的极差由每一对相邻数字的差值相加得来。

接下来考虑，如果 $k=2$ 呢？我们可以从间隔最大的两个数字分开，这样答案就是整个数列的极差减去最大的间隔，以此类推，我们可以删除前 $k-1$ 大的间隔（即从这些地方把数列分开），得到的答案一定是最优解。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n,k;
    cin>>n>>k;
    vector<int> c(n);
    for(int i=0;i<n;i++) cin>>c[i];
    sort(c.begin(),c.end());
    auto last=unique(c.begin(), c.end());
    vector<int> s(c.begin(),last);
    int m=s.size();
    if(m<=k){
        cout<<0<<endl;
        return 0;
    }
    vector<int> v;
    for(int i=1;i<m;i++) v.push_back(s[i]-s[i-1]);
    sort(v.rbegin(),v.rend());
    int sum=0;
    for(int i=0;i<k-1;i++) sum+=v[i];
    int ans=(s.back()-s[0])-sum;
    cout<<ans<<endl;
    return 0;
}

题解

由题意可得，交换 c 数组元素对答案无影响，所以先将 c 数组排序寻找规律。

这样，输入数据 1 可以写成

5 2
-5 0 0 4 10

可以发现，这样子就相当于在数轴上有 $n$ 个点，用 $k$ 条线段（一个点也视作长度为零的线段）覆盖，且线段长度和最小。

对 c 数组进行差分，就可以得到相邻两点的距离（以输入数据 1 为例）。

5 0 4 6

显而易见，我们只需要删去 $k-1$ 个最大间隔，就能得到剩余的 $k$ 条线段长度和最小的线段。

代码

#include<bits/stdc++.h>
using namespace std;
int c[100100];
int main()
{
    int n,k,sum=0;
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>c[i];
    sort(c+1,c+n+1);
    for(int i=1;i<n;i++)
        c[i]=c[i+1]-c[i];
    sort(c+1,c+n);
    for(int i=1;i<=n-k;i++)
        sum+=c[i];
    cout<<sum;
}

题解区都好🍬🍭🍭

#include<bits/stdc++.h>
int n,k,a[100005],c[100005],ans;
int main(){
    std::cin>>n>>k;
    for(int i=1;i<=n;++i)std::cin>>a[i];
    std::sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)c[i]=a[i]-a[i-1];
    std::sort(c+2,c+n+1);
    for(int i=2;i<=n-k+1;++i) ans+=c[i];
    std::cout<<ans;
}