MENU

IncDec序列——差分

February 20, 2019 • Read: 3574 • 算法阅读设置

基本概念——差分

首先定义一个差分数组$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);
    }
}
Archives Tip
QR Code for this page
Tipping QR Code