|
|
|
|
|
##[$AcWing$ $100$. 增减序列](https://www.acwing.com/problem/content/102/)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
给定一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$，每次可以选择一个区间 $[l,r]$，使下标在这个区间内的数都加一或者都减一。
|
|
|
|
|
|
|
|
|
|
|
|
求至少需要多少次操作才能 **使数列中的所有数都一样**，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
|
|
|
|
|
|
|
|
|
|
|
|
**输入格式**
|
|
|
|
|
|
第一行输入正整数 $n$。
|
|
|
|
|
|
|
|
|
|
|
|
接下来 $n$ 行，每行输入一个整数，第 $i+1$ 行的整数代表 $a_i$。
|
|
|
|
|
|
|
|
|
|
|
|
**输出格式**
|
|
|
|
|
|
|
|
|
|
|
|
第一行输出最少操作次数。
|
|
|
|
|
|
|
|
|
|
|
|
第二行输出最终能得到多少种结果。
|
|
|
|
|
|
|
|
|
|
|
|
**数据范围**
|
|
|
|
|
|
$0<n≤10^5,0≤a_i<2147483648$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
4
|
|
|
|
|
|
1
|
|
|
|
|
|
1
|
|
|
|
|
|
2
|
|
|
|
|
|
2
|
|
|
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
1
|
|
|
|
|
|
2
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、题目解析
|
|
|
|
|
|
|
|
|
|
|
|
#### 差分复习
|
|
|
|
|
|
|
|
|
|
|
|
对于一个给定序列 $a$, 它的差分序列 $b$ 定义为：
|
|
|
|
|
|
$$ b[1]=a[1] ① \\ b[i]=a[i]−a[i−1] (2≤i≤n)②$$
|
|
|
|
|
|
|
|
|
|
|
|
可以发现， **前缀和** 、 **差分** 是一对互逆运算，$b$ 序列的前缀和就是 $a$ 序列。
|
|
|
|
|
|
|
|
|
|
|
|
**应用**
|
|
|
|
|
|
如果要把序列 $a$ 的 $[l,r]$ 区间内的所有数加 $d$，差分序列 $b$ 的变化为 $b[l]$ 加 $d$，$b[r+1]$ 减 $d$,减法同理。
|
|
|
|
|
|
|
|
|
|
|
|
#### 本题思路
|
|
|
|
|
|
因为题目中提到在原数组 $a[i]$的某个区间上要么加$1$，要么减$1$,也就是一维数组的区间加减问题，符合 **差分** 的应用场景,使用差分，可以使得原来$r-l+1$次修改变成$2$次，可以节约大量的计算时间，所以，本题应该考虑使用差分。
|
|
|
|
|
|
|
|
|
|
|
|
那我们就需要求出 $a$ 的差分序列 $b$。
|
|
|
|
|
|
|
|
|
|
|
|
题目的最终目标是把数组的全部数字变成一样的，那么，对应到差分数组，就是
|
|
|
|
|
|
$b[1],b[n+1]$是什么值都可以，但$b[2],b[3],...b[n]$都需要等于$0$，并且，$b[1]$的值就是最终数组$a[]$的所有数字一样的那个值。
|
|
|
|
|
|
|
|
|
|
|
|
**以数据样例为例进行理解**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
原始数组： 1 1 2 2
|
|
|
|
|
|
差分数组: 1 0 1 0
|
|
|
|
|
|
```
|
|
|
|
|
|
- $A$方案，前两个$+1$:``` 2 2 2 2 ```
|
|
|
|
|
|
差分数组随之变化,$1$位加$1$，$2+1=3$位减$1$,得到如下的差分数组：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
2 0 0 0
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
- $B$方案，后两个$-1$:``` 1 1 1 1 ```
|
|
|
|
|
|
差分数组随之变化,$3$位减$1$，$4+1=5$位加$1$,得到如下的差分数组：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
1 0 0 0 1
|
|
|
|
|
|
```
|
|
|
|
|
|
**咦？为什么原数组是$4$个数字，你的差分是$5$个数字呢?**
|
|
|
|
|
|
|
|
|
|
|
|
你看一下上面的应用$a[l-r]$加上$d$,是不是$b[l]+=d,b[r+1]-=d$,而$1<=l<=r<=n$
|
|
|
|
|
|
考虑一下边界问题，如果 $r=n$时，上面的
|
|
|
|
|
|
$$b[r+1]-=d \Rightarrow b[n+1]-=d $$
|
|
|
|
|
|
也就是说，$b[]$数组需要考虑到$n+1$项，此时，如果$r=n$时，也就是变化区间最右边到$n$时，就用到了$b[n+1]$,但$b[n+1]$最终是什么值不重要，它的值不影响区间内所有元素的值一样。
|
|
|
|
|
|
|
|
|
|
|
|
**贪心思路求变化最小次数**
|
|
|
|
|
|
|
|
|
|
|
|
> **转化**：题目对 $a$ 序列的 **任何区间加减$1$操作**，等同于对 $b$ 序列中的 **任意两数**，一个加 $1$，一个减 $1$。
|
|
|
|
|
|
> **目标** : 把 $b[2]$ 至 $b[n]$ 全变为 $0$,$b[1],b[n+1]$是多少无所谓。
|
|
|
|
|
|
|
|
|
|
|
|
从 $b[1]$ 至 $b[n+1]$ 中 **任选** 两数的方案进行分类讨论：
|
|
|
|
|
|
|
|
|
|
|
|
由于$b[1],b[n+1]$比较特殊，所以划分分类时，以它们为分类标准进行划分四类：
|
|
|
|
|
|
|
|
|
|
|
|
- **① 选 $b[i]$ 和 $b[j]$**
|
|
|
|
|
|
其中 $2≤i,j≤n$，这种操作会改变 $b[2]$ 至 $b[n]$ 中两个数的值，因为差分操作，无外乎就是：
|
|
|
|
|
|
- 前项$+1$，后项$-1$
|
|
|
|
|
|
- 前项$-1$，后项$+1$
|
|
|
|
|
|
这两种情况，目标是把这段区间所有数字变成$0$,那大于$0$的得$-1$向小了变，小于$0$的得$+1$向大的变。也就是尽量挑 $b[i]$ 和 $b[j]$ **一正一负** 的情况下，这样一下就可以 **变掉两个数**，使得整体向都是$0$的区间逼近。
|
|
|
|
|
|
|
|
|
|
|
|
- **② 选 $b[1]$ 和 $b[j]$**
|
|
|
|
|
|
其中 $2≤j≤n$；这种情况下也是两种可能分支:
|
|
|
|
|
|
- $b[j]>0$,那么$b[j]-=1$,$b[1]+=1$
|
|
|
|
|
|
- $b[j]<0$,那么$b[j]+=1$,$b[1]-=1$
|
|
|
|
|
|
因为我们并不关心$b[1]$的最终值是多少，只关心尽快的把b[2 \sim n]变成$0$,所以，这样一下只能改一个数字，效率不如上面的 ① 快。
|
|
|
|
|
|
|
|
|
|
|
|
- **③ 选 $b[i]$ 和 $b[n+1]$**
|
|
|
|
|
|
其中 $2≤j≤n$；这种情况下也是两种可能分支:
|
|
|
|
|
|
- $b[i]>0$,那么$b[i]-=1$,$b[n+1]+=1$
|
|
|
|
|
|
- $b[i]<0$,那么$b[i]+=1$,$b[n+1]-=1$
|
|
|
|
|
|
因为我们并不关心$b[n+1]$的最终值是多少，只关心尽快的把$b[2 \sim n]$变成$0$,所以，这样一下只能改一个数字，效率不如上面的 ① 快。
|
|
|
|
|
|
|
|
|
|
|
|
- **④ 选 $b[1]$ 和 $b[n+1]$**
|
|
|
|
|
|
因为它不会改变 $b[2]$ 至 $b[n]$ 的值，浪费了操作，一定不是最优解,放弃这种可能。
|
|
|
|
|
|
|
|
|
|
|
|
所以，我们的贪心策略就是：尽量的采用方法 ①,如果实在没有办法使用方法 ①时，再考虑使用方法 ② 或者 方法 ③。
|
|
|
|
|
|
|
|
|
|
|
|
那什么情况下可以使用方法 ① 呢？ 限制条件是在$b[2 \sim n]$中存在$1$个及$1$个以上大于$0$的数字，并且，存在$1$个及$1$个以上小于$0$的数字，才能进行此操作。
|
|
|
|
|
|
|
|
|
|
|
|
所以，有了如下的神操作：
|
|
|
|
|
|
|
|
|
|
|
|
**设 $b[2]$ 至 $b[n]$ 中正数总和为 $p$，负数总和的绝对值为 $q$。**
|
|
|
|
|
|
|
|
|
|
|
|
首先，我们以正负配对的方式执行操作，可执行 $min(p,q)$ 次，剩余 $|p−q|$ 个没有配对。
|
|
|
|
|
|
|
|
|
|
|
|
接下来，剩下的每个与 $b[1]$ 或 $b[n+1]$ 配对，共需 $|p−q|$ 次。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
**综上**，最少操作次数为 $min(p,q)+|p−q|=max(p,q)$ 次。
|
|
|
|
|
|
|
|
|
|
|
|
下面来思考第二个问题：
|
|
|
|
|
|
> **保证最少次数的前提下，最终得到的数列可能有多少种?**
|
|
|
|
|
|
|
|
|
|
|
|
答：在尽量采用方法 ① 的情况下，可以尽快的使得整体区间向全是$0$进行逼近，但最后，随着正数或者负数的消亡，剩下了$|p-q|$个正数值或者负数值，此时，只能通过与$b[1]$或 $b[n+1]$的 **捉对** 操作才能完成整体全是$0$的目标
|
|
|
|
|
|
|
|
|
|
|
|
假设剩下$|p-q|$个：
|
|
|
|
|
|
- $b[1]$消耗掉$0$个，$|p-q|$个交给$b[n+1]$消耗掉
|
|
|
|
|
|
- $b[1]$消耗掉$1$个，$|p-q|-1$个交给$b[n+1]$消耗掉
|
|
|
|
|
|
- $b[1]$消耗掉$2$个，$|p-q|-2$个交给$b[n+1]$消耗掉
|
|
|
|
|
|
...
|
|
|
|
|
|
- $b[1]$消耗掉$|p-q|$个，$0$个交给$b[n+1]$消耗掉
|
|
|
|
|
|
- 共有$|p-q|+1$种情况，此时，$b[1]$的值也随之变化，共$|p-q|+1$种结果。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
typedef long long LL;
|
|
|
|
|
|
const int N = 100010;
|
|
|
|
|
|
|
|
|
|
|
|
int n;
|
|
|
|
|
|
int a[N], b[N];
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
cin >> n;
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
|
|
|
cin >> a[i];
|
|
|
|
|
|
b[i] = a[i] - a[i - 1];
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
LL p = 0, q = 0;
|
|
|
|
|
|
for (int i = 2; i <= n; i++)
|
|
|
|
|
|
if (b[i] > 0)
|
|
|
|
|
|
p += b[i];
|
|
|
|
|
|
else
|
|
|
|
|
|
q -= b[i];
|
|
|
|
|
|
|
|
|
|
|
|
printf("%lld\n%lld\n", max(p, q), abs(p - q) + 1);
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
