增减序列

增减序列

给定一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$,每次可以选择一个区间 $[l,r]$,使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

输入格式

第一行输入正整数 $n$。

接下来 $n$ 行,每行输入一个整数,第 $i+1$ 行的整数代表 $ai$。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

$1≤n≤10^5$,
$0≤a_i<2147483648$

输入样例

1
2
3
4
5
4
1
1
2
2

输出样例

1
2
1
2

解析

需要用到知识点 差分数组

1
2
3
有数组 A[1] A[2] A[3] A[4]
差分数组 B[i] = A[i] - A[i - 1]
可得 A[i] = B[1] + B[2] + B[3] + .... + B[i]

含义:原数组 $A_i$ 是差分数组 $B_i$ 的前 $i$ 项和

知道知识点我们来看题

首先需要实现,快速在 $[l,r]$ 区间内进行加减,根据差分数组的定义,在原数组 $A_i$ 的 $[l,r]$ 上作加减 就相当于在差分数组 $B_i$ 的 $B_l$ 与 $B_{r+1}$ 上作加减

比如样例

1
2
3
4
5
A_i 1 1 2 2
B_i 1 0 1 0
在[1,2]上 +1,则
A_i 2 2 2 2
B_i 2 0 0 0 (B_1 + 1, B_3 - 1)

好了,已经快速解决 $[l,r]$ 上作加减的问题,就可以来看题目的要求了

① 求最少的操作次数

② 输出最终能得到多少种结果

首先来解决①,我们的目的是 让差分数组除 $B_1$ 外的所有数都变成0,那么我们只需要让差分数组 负的加,正的减 就可以保证每次的选择都是最优选择,这个问题很好解决 一个循环即可。

但每次肯定不会正好减到 0,那我们只需要把多出来全部加到 $B_1$ 就好,这样也满足我们的目的。

然后来解决②,考虑①的最后一步,我们除了将多出来的移到 $B_1$,当然还可以移到 $B_{n+1}$,即将多出来的数再 加一减一 变成0(这里可以理解成在自己[l == r]上操作,也可以理解为在整个差分数组外还有一个规则外的区域),那么只需要多出来几就加上几就好(每个数都有两种选择,加到 $B_1$ 上 或者 不加到 $B_1$ 上)

看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <iostream>

const int N = 100005;
long long arr[N], g[N];

int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &arr[i]);
g[i] = arr[i] - arr[i - 1]; //差分数组
}

long long tnt = 0, ans = 0;
for (int i = 2; i <= n; i++) {
if(tnt > 0 && g[i] < 0) ans = ans + std::min(tnt, std::abs(g[i])), tnt = tnt + g[i];
else if(tnt < 0 && g[i] > 0) ans = ans + std::min(std::abs(tnt), g[i]), tnt = tnt + g[i];
//异号的情况 说明有正负出现 正的加,负的减就好
else tnt += g[i]; //同号的情况 那么记录起来就好
}

printf("%lld\n", ans + std::abs(tnt));
//最优情况(负的加,正的减 + 多出来的数(可能是负数,记得取绝对值))
printf("%lld\n", std::abs(tnt) + 1);
//讨论多少种情况 详细看上面解析
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!