【题解】差分数组-codeForces-1197C – Array Splitting

题目链接：

https://codeforces.com/contest/1197/problem/C

题目大概意思是，给出一个不下降序列，定义cost是区间右端点的值减去区间左端点的值。

要求把数组分为n段，求最小的cost。

今下午训练的时候做到这道题我有点懵（毕竟我是菜鸡），然后就观察了一下，发现了一个小现象。把给出的数组的前后两个元素分别相减，就会得到一个新的数组。这个新数组的各个元素之和，就是某一段区间的cost。

然后我大概连蒙带猜地，写了一段代码来解决这个问题。

我最初的思路大概就是分成n段的话，那么把后面k-1个元素各成为一个数组，然后剩下的成为一个数组。

可是！

这样子很明显是错的。举几个例子就知道这样子做是有问题的。所以，这样的代码在第四个测试点就过不了了。那怎么办呢？

当然是换一题来做啦！放弃这题！

所以训练的时候我没有做出这道题，那到底怎么搞？

其实，这道题的思路就是利用前后两个元素相减得到的新数组，也就是差分数组（我训练完上网查了才知道的）差分数组描述了整个序列的变化情况。

开始分析：

当数组只有一段的时候，总的cost就是差分数组的元素和。

当数组分成两段的时候，在分界线处的那个差分元素就可以消掉了。因为，前后两个元素已经分别属于不同的数组了。那么在这里就不需要计算cost了。这个时候，总的cost就要减去这一小段的cost。

当分为更多段的时候，还是一样，只要多出一个分界线，那么就要减去这个分界线处的cost。

于是，问题就转换成了，当把序列分成k段的时候，如何减掉最多的cost。

分成k段，就是形成k-1个分割线，也就是减去k-1个cost。

我们只需要减去最大的k-1个cost，就能得到最小的cost。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int>m;
int num[300005];

int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0;i <n;i++)
	{
		cin >> num[i];
	}
	for (int i = 1; i < n; i++)
		m.push_back(num[i] - num[i - 1]);
	int cost = 0;
	sort(m.begin(),m.end());

	cost = num[n-1] - num[0];
	
	for (int i =n-2;i>=n-k;i--)
		cost -= m[i];
	cout << cost << endl;
}