P4552 IncDec Sequencet题解

Faulkner

2024 年 03 月 03 日

747 次浏览

2 条评论

1577字数

默认分类

# [Poetize6] IncDec Sequence

## 题目描述

给定一个长度为 $n$ 的数列 ${a_1,a_2,\cdots,a_n}$，每次可以选择一个区间$[l,r]$，使这个区间内的数都加 $1$ 或者都减 $1$。

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

## 输入格式

第一行一个正整数 $n$
接下来 $n$ 行,每行一个整数,第 $i+1 $行的整数表示 $a_i$。

## 输出格式

第一行输出最少操作次数
第二行输出最终能得到多少种结果

## 样例 #1

### 样例输入 #1

```
4
1
1
2
2
```

### 样例输出 #1

```
1
2
```

## 提示

对于 $100\%$ 的数据，$n\le 100000, 0 \le a_i \le 2^{31}$。

## 分析

这是差分的一种运用。

首先，需要明白（如有不明白，请先补习相关知识）：对于一个序列，当某一个区间内（此区间长度大于二）的所有元素上加上一个相同的值（该值可以是负数）时，在差分数组中，我们需在区间的起始位置加上这个值，而在区间的终点的下一个位置减去这个值。这个概念是此题核心。

分析一个所有元素都是相同的值的序列，我们可以轻易得出其差分数组的特点：首元素等于该序列的值，其余元素均为0。因此，通过对差分数组进行适当的操作，使其符合这一特征，我们便能构造出一个所有元素值相同的序列。

稍加思索便可以得到一个策略：我们将首元素拿开，只考虑后面所有元素的差分数组，我们的目标是将其全部变为0。

现在我们在差分数组中考虑任一正值，要将其降至0至少需要它的值那么多次减操作，同理，降低负值至0亦需同等数量的加操作。因此可以得出结论：对所有正值而言，将它们降至0至少需要所有正数的和那么多步骤，对负值而言同理。

而通过上述概念又可以得出结论：当差分数组同时存在正负值时，我们能够同时处理**某一对**正值和负值，且此操作不会互相影响，而最后当差分数组中的正值或负值之一被完全处理后，剩余值的处理则需依次一步步进行，对应于原序列中只有单个元素的区间进行加或者减操作。因此，整个过程的最少步骤数是由差分数组中所有正值的和与所有负值的和的绝对值之间的较大者所决定。

而这也是所需的最小步骤，我们可以用反证法证明。假设 $S_+$ 是差分数组中所有正数的和，$S_-$ 是所有负数的和的绝对值。如果我们尝试用少于 $\max(S_+, S_-)$ 的步数将数组 $A$ 的所有元素变为0，那么至少会有一个正数或负数在差分数组中没有完全被消除。这与原目标相悖。

而解数量便是**正数和负数和的绝对值的差值的绝对值加上一**，这很容易便可以想到，就不多做说明。

## AC代码

```c++
// P4552 [Poetize6] IncDec Sequence
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
LL a[N], b[N];

void insert(int l, int r, int x)
{
    b[l] += x;
    b[r + 1] -= x;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        insert(i, i, a[i]);
    }
    LL pos = 0, neg = 0;
    for(int i = 2; i <= n; i++)
    {
        if(b[i] > 0) pos += b[i];
        if(b[i] < 0) neg -= b[i];
    }
    LL res = abs(pos - neg) + 1;
    LL ans = max(pos, neg);
    printf("%lld\n%lld", ans,res);
}
```

最后修改：2024 年 10 月 23 日