「Codeforces 1197C」Array Splitting

Description

给出一个长度为 $n$ 的单调不下降序列 $\{ a \}$，现要将其分成 $k$ 段，使得每一段的极差的和最小，求这个最小的和（每段长度至少为 $1$，当长度为 $1$ 时，其极差为 $0$）。

$(1 \leq k \leq n \leq 3 \times 10^5,1 \leq a_i \leq 10^9, \forall a_i \geq a_{i - 1})$

Source

[Luogu]CF1197C

[Codeforces]1197C

Solution

直接求似乎很难？考虑转化问题。

我们不妨把分成 $k$ 段看作断开 $k - 1$ 处，假设我们断在了第 $i$ 个数和第 $i + 1$ 个数中间，那么第 $i$ 个数贡献为正，第 $i + 1$ 个数贡献为负，贡献和为 $a_i - a_{i + 1}$ 。

显然我们让断开的地方贡献和最小时最优，因此我们可以预处理出 $f_i = a_i - a_{i + 1}$，然后将 $f$ 数组从小到大排序，选前 $k - 1$ 个的和即可。第 $1$ 个数的贡献为负，第 $n$ 个数的贡献为正，这里没有算进去，所以最后应当加上 $a_n - a_1$ 。时间复杂度为排序的复杂度 $O(n \log n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}
 
template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
 
const int MAXN = 3e5;
int n, k, a[MAXN + 5], f[MAXN + 5];
LL ans;
 
int main() {
    read(n), read(k);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        f[i - 1] = a[i - 1] - a[i];//转化为相邻两数之差 
    }
    sort(f + 1, f + n + 1);//从小到大排序 
    ans = a[n] - a[1];
    for (int i = 1; i < k; ++i) ans += f[i];//取前 k - 1 个 
    write(ans);
    putchar('\n');
    return 0;
}