建立两个数组读入数据,建立一个差值数组记录他们的差值
要求第一个数组怎么变成第二个数组的值
也就转换成了怎么样才能让这个差值数组变成0,操作方式有2种:
1. 选择任意两项, 一项加1, 另一项减1
2. 选择任意一项 加1 或者 减1
使数组全部变为0的最少操作方案就是 差分数组中负数和与正数和的绝对值的最大值
java代码如下:
import java.util.*;
public class Main {
static final int N = 100010;
static int[] a = new int[N], b = new int[N], t = new int[N];
public static void insert(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 ++) t[i] = a[i] - b[i];
for (int i = n; i > 0 ; i -- ) t[i] -= t[i - 1];//倒着减,因为正着减的话i-1的数值已经发生变化
int pos = 0, neg = 0;
for (int i = 1; i <= n; i ++) {
if (t[i] > 0) pos += t[i];
if (t[i] < 0) neg -= t[i];
}
System.out.println(Math.max(pos, neg));
}
}