题目
摆玩具【算法赛】
https://www.lanqiao.cn/problems/5888/learning/?contest_id=145
问题描述
小蓝是一个热爱收集玩具的小伙子，他拥有 n 个不同的玩具。
这天，他把 n 个玩具按照高度顺序从矮到高摆放在了窗台上，然后，他希望将这些玩具分成 k 个段，使得所有分段的极差之和尽可能小。
具体来说，你需要将一个长度为 n 的序列分为 k 段，我们定义 Gi 为第 i 个分段的极差，你要最小化 ∑i=1kGi。
你能帮助小蓝找到最小值是多少吗？
极差：是指每个分段中最高和最矮玩具高度之差，例如有一段为：{3,6,10,12}{3,6,10,12}，那么极差为 12−3=912−3=9。
分段：即每一段在原始序列中是一段连续区间，例如将 {1,2,3,4,5}{1,2,3,4,5} 分为两段，{1,2,3}∣{4,5}{1,2,3}∣{4,5} 是合法的，但是 {1,2,4}∣{3,5}{1,2,4}∣{3,5} 不是合法的。
输入格式
第一行输入两个整数 n,k，代表玩具数量和需要分段的数量。
第二行输入 n 个整数 {h1,h2,...,hn}，代表每个玩具的高度。
输出格式
输出一个整数，表示最小的极差和。
样例输入
5 2
2 5 7 10 13
样例输出
8
说明
存在多种分段方式，其结果都是最小值：
- {2}∣{5,7,10,13}{2}∣{5,7,10,13}，极差和为 0+8=80+8=8。
- {2,5,7}∣{10,13}{2,5,7}∣{10,13}，极差和为 5+3=85+3=8。
- {2,5,7,10}∣{13}{2,5,7,10}∣{13}，极差和为 8+0=88+0=8。
不存在其他方案使得答案小于 88。
评测数据范围
1≤k≤n≤105 。
1≤h1≤h2≤h3≤...≤hn≤109 。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Java | 2s | 128M |
| Python3 | 3s | 128M |
| PyPy3 | 3s | 128M |
思路和解题方法
#include <iostream>和#include <algorithm>：这两行代码包含了所需的头文件，分别用于输入输出操作和排序操作。
int n;和int k, a[100005],b[100005];：这部分代码定义了三个整型变量n、k和两个整型数组a、b。其中，n表示序列中元素的数量，k表示要删除的元素的数量，a保存原始序列中的元素，b保存相邻元素之间的差值。
void solve()：这部分代码定义了一个函数solve，用于解决问题。
cin >> n >> k;：使用输入流cin读取用户输入的序列长度n和要删除的元素数量k。
for (int i = 0; i < n; i++) cin >> a[i];：使用循环结构for，依次读取用户输入的序列中的元素，并将它们存储在数组a中。
for (int i = 1; i < n; i++) b[i-1]=a[i]-a[i-1];：使用循环结构for，计算相邻元素之间的差值，并将它们存储在数组b中。注意，数组b的下标从0开始。
sort(b,b+n-1);：使用sort函数，对数组b中的元素进行排序。由于数组b中只有n-1个元素，所以第二个参数为n-1。
int sum=0; for(int i=0;i<n-k;++i) {sum+=b[i];}：使用循环结构for，计算前n-k个最小的差值之和，并将结果存储在变量sum中。
cout << sum;：使用输出流cout将结果输出到控制台。
int main()：这部分代码定义了主函数main，是程序的入口点。
solve();：调用函数solve解决问题。
return 0;：返回0表示程序正常结束。
复杂度
时间复杂度:
O(n*logn)
时间复杂度分析：
- 输入序列的长度为n，需要遍历n个元素，所以输入的时间复杂度为O(n)。
- 计算相邻元素之间的差值并存储到数组b中，需要遍历n-1个元素，所以该步骤的时间复杂度为O(n)。
- 对数组b进行排序，排序的时间复杂度为O(nlogn)。
- 计算前n-k个最小差值的和，需要遍历n-k个元素，所以该步骤的时间复杂度为O(n)。
- 输出结果的时间复杂度为O(1)。
代码的总时间复杂度为O(nlogn)。
空间复杂度：
O(n)
空间复杂度分析：
- 数组a和数组b的长度都为n，所以它们的空间复杂度均为O(n)。
- 其他变量占用的空间可以忽略不计。
c++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int n; // 存储序列的长度
int k, a[100005], b[100005]; // k表示要删除的元素数量，a存储原始序列的元素，b存储相邻元素的差值
void solve() {
cin >> n >> k; // 输入序列的长度和要删除的元素数量
for (int i = 0; i < n; i++)
cin >> a[i]; // 输入序列的元素并存储到数组a中
// 计算相邻元素之间的差值并存储到数组b中
for (int i = 1; i < n; i++)
b[i-1] = a[i] - a[i-1];
sort(b, b+n-1); // 对数组b进行排序
int sum = 0;
for (int i = 0; i < n-k; ++i) {
sum += b[i]; // 计算前n-k个最小差值的和
}
cout << sum; // 输出结果
}
int main() {
solve(); // 调用solve函数解决问题
return 0;
}
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
