变量

题目大意

​ 给定一个长度为 $n$ 的序列 $c$ 去重后，用 $k$ 个区间完全覆盖这个序列,问 $k$ 个区间长度和的 最小值 为多少

分析

​ 先对序列 $c$ 去重,对序列 $c$ 做差分

​ 得到差分数组 $d$

​ 观察到

​ 当 $k = 1$ 时 $res = \sum d$

​ 当 $k > 1$, 每划出一个区间相当于答案减去 $ d_i$ ，故为使 $res$ 最小从大到小减去 $d_i$ 即可

Code

int n,k;

signed main()
{
    cin >> n >> k;
    vector<int> a;
    for(int i = 0;i < n;i++){
        int x;cin>>x;
        a.push_back(x);
    }
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    vector<int> b;
    for(int i = 1; i < a.size();i++)
        b.emplace_back(a[i] - a[i-1]);
    sort(b.begin(),b.end(),greater<int>());
    int res = 0;
    for(auto k:b) res += k;

    for(int i = 2;i <= k;i++){
        res -= b[i-2];
    }
    cout << res << endl;
        
    return 0;
}