$O(n)$
理解难点:
1. 为什么a[]变为0即等价于让b[]全变为0
a[] = p[] - t[] 表示需要改变的值 b[]为a[]的差分数组
那么反过来 a[]就是b[]的前缀和数组,那么前缀和数组全为0了,原数组就需要全变为0
2. 为什么最小次数就是正数的和 与 负数的和的绝对值 之前的最大值
因为a[]的变化规则是一段连续的数组+1或-1
那么等价于差分数组 任选2数,一数+1另一数-1 或者 一数-1另一数+1
如果正数和负数可以凑成一对就可以一并处理,如果最后剩下单个的负数或正数,就逐个处理。所以取正数和与负数和之间的最大值
n = int(input())
p = [0 for _ in range(n + 2)]
t = [0 for _ in range(n + 2)]
p[1:] = list(map(int, input().split()))
t[1:] = list(map(int, input().split()))
a = [0 for _ in range(n + 2)]
b = [0 for _ in range(n + 2)]
for i in range(1, n + 1):
a[i] = p[i] - t[i] # 计算p[] - t[], 需要改变的值
pos = 0 # 记录正数的和
neg = 0 # 记录负数的和的绝对值
for i in range(1, n + 1):
b[i] = a[i] - a[i - 1] # 计算差分数组
if b[i] > 0:
pos += b[i]
else:
neg -= b[i]
print(max(pos, neg))