题解 CF1197C 【Array Splitting】
Heartlessly
2019-07-23 19:00:52
## 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;
}
```