增减序列
增减序列
给定一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$,每次可以选择一个区间 $[l,r]$,使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
输入格式
第一行输入正整数 $n$。
接下来 $n$ 行,每行输入一个整数,第 $i+1$ 行的整数代表 $ai$。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
$1≤n≤10^5$,
$0≤a_i<2147483648$
输入样例
1 |
|
输出样例
1 |
|
解析
需要用到知识点 差分数组
1 |
|
含义:原数组 $A_i$ 是差分数组 $B_i$ 的前 $i$ 项和
知道知识点我们来看题
首先需要实现,快速在 $[l,r]$ 区间内进行加减,根据差分数组的定义,在原数组 $A_i$ 的 $[l,r]$ 上作加减 就相当于在差分数组 $B_i$ 的 $B_l$ 与 $B_{r+1}$ 上作加减
比如样例
1 |
|
好了,已经快速解决 $[l,r]$ 上作加减的问题,就可以来看题目的要求了
① 求最少的操作次数
② 输出最终能得到多少种结果
首先来解决①,我们的目的是 让差分数组除 $B_1$ 外的所有数都变成0,那么我们只需要让差分数组 负的加,正的减 就可以保证每次的选择都是最优选择,这个问题很好解决 一个循环即可。
但每次肯定不会正好减到 0,那我们只需要把多出来全部加到 $B_1$ 就好,这样也满足我们的目的。
然后来解决②,考虑①的最后一步,我们除了将多出来的移到 $B_1$,当然还可以移到 $B_{n+1}$,即将多出来的数再 加一减一 变成0(这里可以理解成在自己[l == r]上操作,也可以理解为在整个差分数组外还有一个规则外的区域),那么只需要多出来几就加上几就好(每个数都有两种选择,加到 $B_1$ 上 或者 不加到 $B_1$ 上)
看代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!