题解 CF1197C 【Array Splitting】

Heartlessly

2019-07-23 19:00:52

Solution

## 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})$ ## 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 ```cpp #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; } ```