【题解】差分数组-codeForces-1197C – Array Splitting
数组 Array 题解 差分 Codeforces
2023-06-13 09:14:15 时间
题目链接:
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;
}
相关文章
- javabyte数组转string_byte数组转string
- javaScript中创建数组的3种方式
- Linux shell awk数组使用
- leetcode-189. 旋转数组
- 1.1 5368. 找出数组中的幸运数(1394. Find Lucky Integer in an Array)
- C++通过array实现二维数组
- vector subscript out of range数组下标越界错误「建议收藏」
- 字节数组转化为字符串_数组字符串
- Scala 【 4 参数、过程以及数组 Array 和 ArrayBuffer 】
- 解决PostgreSQL 数据库数组 Array使用中的一些小问题
- Java中对Array数组的常用操作详解编程语言
- Javascript中的Array(数组) 、{}(映射) 与JSON解析详解编程语言
- Java数组转ArrayList的注意事项详解编程语言
- PHP array_unshift():在数组开头插入元素
- perl列表和数组变量详解
- 深思PHP数组遍历的差异(array_diff的实现)
- php合并数组array_merge函数运算符加号与的区别
- 对象无length属性时IE6/IE7中无法将其转换成伪数组(ArrayLike)
- php数组函数序列之shuffle()和array_rand()随机函数使用介绍
- php数组函数序列之array_slice()-在数组中根据条件取出一段值,并返回
- 解析dom中的children对象数组元素firstChild,lastChild的使用
- js中数组Array的一些常用方法总结
- php二维数组排序方法(array_multisortusort)
- 约瑟夫环问题(数组法)c语言实现
- 实例讲解JS中数组Array的操作方法
- C++中关于[]静态数组和new分配的动态数组的区别分析