题目描述

一维差分

样例

import java.util.*;

public class Main {

    /*
      将现温度减去舒适温度，得到差值数组，再去得到差值数组的差分数组。

      如果现温度等于舒适温度，差值数组应该为0，差值数组对应的差分数组元素应该全为0.
      问题就转换到把差值数组对应的差分数组的值全部变为0

      任取一个正数减1，任取一个负数加一
      差分数组各元素的和一定为0，说明正数总合=负数总合，即正数总合=负数总合=最少操作次数

      要注意，差分数组的长度是n+1

    */

    static final int N = 100010;
    static int[] a = new int[N], b = new int[N], t = new int[N];
    public static void difference(int l, int r, int c) {
        t[l] += c;
        t[r + 1] -= c;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i ++) a[i] = sc.nextInt();
        for (int i = 1; i <= n; i ++) b[i] = sc.nextInt();
        for (int i = 1; i <= n; i ++) difference(i, i, b[i] - a[i]);

        int res = 0;
        for (int i = 1; i <= n + 1; i ++) {
            if (t[i] > 0) res += t[i];
        }
        System.out.println(res);
    }
}