题解 CF1197C 【Array Splitting】

感觉这题没有蓝题难度吧，CF的题恶评太严重了。

言归正传，我们考虑先分成 $n$ 段，然后合并成 $k$ 段。

每次计算合并后造成的影响，合并影响最小的。

以样例1为例：

6 3
4 8 15 16 23 42

计算两数之间的差值为：4，7，1，7，19

我们分别将差值为1，4，7的两个数合并，合并后原序列变成4_8，1523，42（或者4~16，23，42），统计后得到答案为12。

考虑如何方便计算。

我们可以先计算 $a[n]-a[1]$ 的差值，在减去没有被合并的差值。这里可以用堆来找出前 $n$ 小的差值贪心地来合并（当然排序也行了）

时间复杂度 $O(n\ log\ n)$

最后放代码：

#include<iostream>
#include<queue>
#include<algorithm> 
#include<functional>
using namespace std;
int a[300005];
priority_queue<int,vector<int>,greater<int> > pq;
int main(){
	int n,sum,k;
	cin>>n>>k;sum=n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n-1;i++){
		pq.push(a[i+1]-a[i]);//计算差值
	}
	while(sum>k){
		pq.pop();
		sum--;//找到前k小差值
	}
	int ans=a[n-1]-a[0];
	while(!pq.empty()){
		ans-=pq.top();//计算答案
		pq.pop();
	}
	cout<<ans;
	return 0;
}

题解 CF1197C 【Array Splitting】

关于