蓝桥杯双周赛-526互联

2-C

题意：

把n个数分成k个子序列，子序列要求连续，问怎么样分使得每组的极差之和最小

思路：

首先最优解是什么样的，必然是形如[\(l_{1}\) , \(r_{1}\)], [\(l_{2}\) , \(r_{2}\)]...这样的一段一段，
那么这两段为什么要分开呢？因为(\(r_{1}\), \(l_{2}\))的差值我们无法接受，所以在所有这样的断口中前 K - 1大的不要

inline void solve() 
{
	int n, k; cin >> n >> k;
	std::vector<int> a(n);

	for (int i = 0; i < n; i++) cin >> a[i];

	vector<int> d;
	for (int i = 1; i < n; i++) d.pb(a[i] - a[i - 1]);
	sort(d.begin(), d.end());
	
	LL ans = 0;
	for (int i = 0; i < n - k; i++) // size = n - 1 - (k - 1) = n - k
		ans += d[i];

	cout << ans << endl;
}