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);
    }
}