---

摆玩具[算法赛]（差分）

原创 于 2023-10-26 10:27:01 发布 · 粉丝可见 · 182 阅读 · 1 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/134049755

本题链接： 用户登录

题目：

样例：

cobol<br/>5 2<br/>2 5 7 10 13<br/>

8

思路：

由题意，这是一个递增的数组，其次要求最小的极差，对 数组 进行分成 k 个分段数组。

由于是一个递增的数组，且极差的求值，我们应该联想到 前缀和 或者 极差 的知识点。

我们构造差分数组，求出相邻之间的差值，对差分数组进行排序，丢弃相应的 k 个极差最大的组，剩下的就是最小的极差了。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
int a[N],n,k;	// 原数组
 
int b[N],idx = 1;// 差分数组
 
inline  bool cmp(int &a,int &b)
{
	return a > b;
}
 
inline void solve()
{
	// 输入n，k 以及 原数组
	cin >> n >> k;
	
	for(int i = 1;i <= n;++i) cin >> a[i];
	
	// 构造差分数组
	for(int i = 2;i <= n;++i) b[idx++] = a[i] - a[i - 1];
	
	// 将极差大的 放在前面
	sort(b + 1,b + idx + 1,cmp);
	
	int ans = 0;	// 存储的最少极差值
	
	// 这里 我们去掉相应的 k 个分段 的 最大极差值
	// 累加剩余的 最少极差值，就是我们分段后的最少极差值
	
	for(int i = k;i <= idx;++i)
	{
		ans += b[i];
	}
	
	cout << ans << endl;
}
 
int main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：