AcWing — IncDec序列(差分+贪心)
发布日期:2021-07-01 00:18:48
浏览次数:3
分类:技术文章
本文共 1379 字,大约阅读时间需要 4 分钟。
题目链接:
时空限制:10s / 256MB题目描述
给定一个长度为 n 的数列a1,a2,…,an,每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。输入格式
第一行输入正整数n。
接下来n行,每行输入一个整数,第i+1行的整数代表ai。输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。数据范围
0<n≤10^5, 0≤ai<2147483648
输入样例
4
1 1 2 2
输出样例
1
2
解题思路
首先我们来介绍一下差分是什么东西:
1. 差分定义
- 定义一个差分数组S和一个原数组A。
- p[1]=a[1], p[i]=a[i]-a[i-1]
2. 差分性质
- A数组的差分数组的前缀和数组就等于原数组,即S[i]=a[i]=p[i]+S[i-1]
- S数组的差分数也等于差分数组,即p[i]=S[i]-S[i-1]
- 还有比较重要,而且常用的的一条,我们在修改某一段区间的时候,比如这道题的集体加 e 的时候,将操作放在差分数组上就变成了p[l]+=e,p[r+1]-=e这样,我们就可以把区间操作更改为单点操作,很大的减少了时间复杂度。
- 当然,差分的运用远不止于此,在树上等也是可以进行差分操作的。
综上:有了这些性质,我们在做一些题的时候就可以将其转换为差分数组求解,完成过后过一遍前缀和得到正确答案。
说了这么多,就来看看这一题怎样做吧。
3. 本题题解
- 因为是区间整体加减1,所以我们很自然的就可以想到用差分求解。
- 这道题可以看做求出原序列的差分之后,将差分数组p[2...n]全部变为0所需的最少的步数和可以使p[1]变为多少种不同的数。
- 贪心操作: 很明显,在我们求出的差分数组中,有正数也有负数,要消除这些数,使得它们全部归零。,我们可以让正数减1,负数加1,这样就可以快速的转化成目标0。有可能pos!=neg,那么就让剩余的和p[1]或p[n+1]配对。
- 经过上述分析,我们就能够推导出本题的最小次数公式:
- ans=min(pos,neg)+abs(pos-neg)=max(pos,neg);
- 最后我们还要求能构成几组解, 这很容易可以推出: ans=abs(pos-neg)+1
Accepted Code:
#includeusing namespace std;int main() { int a, b, n, cnt; long long pos = 0, neg = 0; scanf("%d", &n); scanf("%d", &a); for (int i = 1; i < n; i++) { scanf("%d", &b); cnt = b - a; if (cnt > 0) pos += cnt; else neg -= cnt; a = b; } printf("%lld\n%lld\n", max(pos, neg), llabs(pos - neg) + 1); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/92075599 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月22日 05时25分22秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
how2heap-fastbin_dup_consolidate
2019-04-30
tf keras SimpleRNN源码解析
2019-04-30
MyBatisPlus简单入门(SpringBoot)
2019-04-30
攻防世界web进阶区web2详解
2019-04-30
xss-labs详解(上)1-10
2019-04-30
xss-labs详解(下)11-20
2019-04-30
攻防世界web进阶区ics-04详解
2019-04-30
sql注入总结学习
2019-04-30
Python实现决策树 Desision Tree & 可视化
2019-04-30
MATLAB与CUDA
2019-04-30
Linux png转jpg (convert命令)
2019-04-30
Ubuntu更新后终端中字体的颜色全是白色
2019-04-30
vscode git
2019-04-30
基于MATLAB的二进制数字调制与解调信号的仿真——2PSK
2019-04-30
基于MATLAB的模拟调制信号与解调的仿真——DSB
2019-04-30
HDU - 1166 敌兵布阵 (树状数组模板题/线段树模板题)
2019-04-30
CodeForces - 456C Boredom (dp)
2019-04-30
CodeForces - 675A Infinite Sequence(简单数论 细节)
2019-04-30
CodeForces - 1042B Vitamins (思维)
2019-04-30