IncDec序列——差分

基本概念——差分

首先定义一个差分数组$d$和原数组$A$

则有$d[1]=A[1]$，$d[i] = A[i]-A[i - 1](2<=i<=n)$

差分性质

差分数组有一些特别的性质

1. $A$数组的差分数组的前缀和数组就等于$A$数组
2. 对原数组$[L,R]$区间的值统一加上（减去）$C$，其实就等于对差分数组$d[L] += C, d[R + 1] -= C$

上面第二个性质比较重要，因为可以把区间操作改为单点操作，巨幅减少时间复杂度

回到题目

这道题可以看作求出原序列的差分之后，将$d[2],...,d[n]$全部变为0所需的最少步数，和可以使$d[1]$变为多少种不同的数

很明显，在我们求出的差分数组中，有正有负，要消除这些数使得它们全部归零，有以下三种操作：

1. 选取一个正数$x$和一个负数$y$，使正数减1，负数加1，这样经过多次操作，一定可以以最少的代价将绝对值较小的一方归零，代价为$abs(min(x,y))$
2. 选取一个正数$x$，使其与$d[1]$配对，这样我们经过多次操作，一定可以将它归零，代价为$abs(x)$
3. 选取一个负数$y$，使其与$d[1]$配对，这样我们经过多次操作，一定可以将它归零，代价为$abs(y)$

经过上述分析，我们就能推导出本体的解题公式：

$$ ans = abs(min(x,y)) + abs(x - y) = abs(max(x,y)) $$

最后还要求能构成几组解，这个很容易推出

$$ ans = abs(x - y) + 1 $$

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        Long[] arr = new Long[n + 1];
        Long[] d = new Long[n + 1];
        arr[1] = cin.nextLong();
        d[1] = arr[1];
        for (int i = 2; i <= n; i++) {
            arr[i] = cin.nextLong();
            d[i] = arr[i] - arr[i - 1];
        }
        long z = 0L, f = 0L;
        for (int i = 2; i <= n; i++) {
            if (d[i] > 0)
                z += d[i];
            else
                f -= d[i];
        }
        System.out.println(Math.max(z, f));
        System.out.println(Math.abs(z - f) + 1);
    }
}