题目链接:https://www.acwing.com/problem/content/description/102/
时空限制：10s / 256MB

题目描述

给定一个长度为 n 的数列a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

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

输出格式

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

数据范围

0<n≤10^5, 0≤ai<2147483648

输入样例

4
1
1
2
2

输出样例

1
2

解题思路

首先我们来介绍一下差分是什么东西:

1. 差分定义

  • 定义一个差分数组S和一个原数组A。
  • p[1]=a[1], p[i]=a[i]-a[i-1]

2. 差分性质

  • A数组的差分数组的前缀和数组就等于原数组,即S[i]=a[i]=p[i]+S[i-1]
  • S数组的差分数也等于差分数组，即p[i]=S[i]-S[i-1]
  • 还有比较重要，而且常用的的一条，我们在修改某一段区间的时候，比如这道题的集体加 e 的时候，将操作放在差分数组上就变成了p[l]+=e,p[r+1]-=e这样，我们就可以把区间操作更改为单点操作，很大的减少了时间复杂度。
  • 当然，差分的运用远不止于此，在树上等也是可以进行差分操作的。

综上：有了这些性质，我们在做一些题的时候就可以将其转换为差分数组求解，完成过后过一遍前缀和得到正确答案。

说了这么多，就来看看这一题怎样做吧。 

3. 本题题解

  • 因为是区间整体加减1，所以我们很自然的就可以想到用差分求解。
  • 这道题可以看做求出原序列的差分之后，将差分数组p[2...n]全部变为0所需的最少的步数和可以使p[1]变为多少种不同的数。
  • 贪心操作: 很明显，在我们求出的差分数组中，有正数也有负数，要消除这些数，使得它们全部归零。，我们可以让正数减1，负数加1，这样就可以快速的转化成目标0。有可能pos!=neg,那么就让剩余的和p[1]或p[n+1]配对。
  • 经过上述分析，我们就能够推导出本题的最小次数公式:
  • ans=min(pos,neg)+abs(pos-neg)=max(pos,neg);
  • 最后我们还要求能构成几组解, 这很容易可以推出: ans=abs(pos-neg)+1

Accepted Code:​​​​​​​

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, n, cnt;
    long long pos = 0, neg = 0;
    scanf("%d", &n);
    scanf("%d", &a);
    for (int i = 1; i < n; i++) {
        scanf("%d", &b);
        cnt = b - a;
        if (cnt > 0)
            pos += cnt;
        else neg -= cnt;
        a = b;
    }
    printf("%lld\n%lld\n", max(pos, neg), llabs(pos - neg) + 1);
    return 0;
}