洛谷P4552 [Poetize6] IncDec Sequence 题解

题目链接：P4552 [Poetize6] IncDec Sequence

题意：

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

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

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

这道题思路比较有趣，代码很简单但是相对来说不好想

本文比较长，建议耐心阅读（当然也可以直接 ⌘+w 或者 ctrl+w 啦）

差分，常用于 \(O(1)\) 区间加减，全局询问

对于这种看上去也不是用数据结构做的题目，

考虑差分。差分数组 \(b_i\) 的定义为 \(b_i = a_i-a_{i-1}\)

容易发现 \(a_i = \sum_{1 \le j \le i}b_i\) ，值得注意的是， \(a_1 = b_1\)

对于区间 \([l,r]\) 加 \(1\) 的修改，只要把 \(b_l\) 加上 \(1\) ，\(b_{r+1}\) 减去 \(1\) 就可以了

然后问题就转化为了将 \(b_2,b_3,\dots,b_n\) 都变成 \(0\) 的最小花费

观察差分的性质，其实每次修改就是在搬运一个 \(1\) ，

也就是把它从 \(b_l\) 搬到 \(b_{r+1}\) ，或者反过来搬

对于每个合法的修改，一定可以完成这样的操作

可以发现当 \(r=n\) 时会出现从外面搬过来或者搬到外面去的情况

先不急，我们先考虑 \(r<n\) 时

显然我们可以把所有的 \(b_i<0\) 和 \(b_j >0\) 配对（ \(2 \le i \le j \le n\) ），然后相互抵消

可以发现这样配对消去的最小花费为 \(\min(p,q)\)

其中 \(p= \sum_{1 \le i \le n} [b_i<0],~q= \sum_{1 \le i \le n} [b_i>0]\)

这样配对也会出现最后消不完的情况，

这个时候我们就可以把它们与 \(n+1\) 配对，或者 \(b_1\)

这样的答案是 \(\operatorname{abs}(p-q)\)

则最后的答案就是 \(\min(p,q)+\operatorname{abs}(p-q)=\max(p,q)\)

再看第二问，其实很简单

看我们的最后一步，如果和 \(b_1\) 配对 \(k\) 次，最后的 \(a_i\) 就会变成 \(b_1+k\)

所以方案数就是 \(\operatorname{abs}(p-q)+1\) （不与 \(b_1\) 配对也是一种情况）

然后就好了，时间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

int n,p,q,a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    for(int i=2; i<=n; i++)
    {
        int c=a[i]-a[i-1];
        c>0?p+=c:q-=c;
    }
    cout << max(p,q) << '\n' << abs(p-q)+1 << '\n';
    return 0;
}