---
title: "增减序列"
created: 2025-11-28
tags:
  - 算法
---

# 增减序列

## 题目 [增减序列](https://www.acwing.com/problem/content/102/)

![[image-64d0e6c3.png]]

## 思路分析

需要对差分有比较深入的理解

要让原数组全一样 那就意味着要让差分数组从第二项开始全为0 这个能理解吧（b[1]=a[1]）

用贪心的思想，来使得b中所有数变成零

显然做b[L]++,b[R+1]--;操作的时候 找两个数配对 负数++ 正数-- 两两相消变0

此时的操作总次数为 min(pos,neg)      其中pos为差分数组中正数和 neg为负数和

但是最终结果可能依然不是全 0的，因为 abs(sum(正数))可能！=abs(sum(负数))

在经过上面的操作后 如果还有剩下 就一定剩下了同符号的数

怎么把这些同符号的数消掉

只能通过b[1]或者b[n+1]这两个对差分数组没有影响的数 来一个一个的把自己减为0

所以操作次数为个数的总和，abs(pos-neg);

综上 最少操作次数——  min(pos,neg) + abs(pos-neg)

还有一个问题 问有多少种结果

很容易知道 数列的值就是b[1]的值，根据逆推，原数组(也就是我们的数列)是差分数组的前缀和

根据前缀和的公式，s[i] = s[i-1] + b[i]

由于b[2]-b[n]都为0，故s[i] = s[i-1] = b[1]

所以我们对b[1]的操作次数也就是种类数量

由于贪心的去操作，一开始是对负数和正数两个点进行操作，所以b[1]没有变

之后数组就只剩下同符号的数

此时我们有两种方案

假设此时数组只剩下正数

方案一       b[1] += 1,b[i+1] -=1

方案二       b[i] -= (-1),b[n+1] += (-1)

因为最后的效果相同均是将2-n的数减为0，故两种方案均可

举例两个边界情况，如果只采取方案二，b[1]不变

如果只采取方案一，即需要操作abs(pos-neg)次，b[1] += abs(pos-neg);

假设一开始b[1]为2，abs(pos-neg)为3，b[1]的取值可能为2,3,4,5，即abs(pos-neg)+1

综上 结果数量—— abs(pos-neg)+1

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=1e5+10;
int b[N],a[N];
int n;
LL pos,neg;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }

    for(int i=2;i<=n;i++){
        if(b[i]>0)  pos+=b[i];
        else    neg-=b[i];
    }
    cout<<min(pos,neg)+abs(pos-neg)<<endl;
    cout<<abs(pos-neg)+1<<endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[合格数|合格数]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/前缀和与差分相关模型/差分/岛|岛]]