AcWing 100. 增减序列
原题链接
中等
作者:
皓首不倦
,
2020-09-15 19:26:11
,
所有人可见
,
阅读 463
'''
将原序列转换成差分序列,每次操作区间相当于在0, 1, 2, .... n这些点中选2个点
一个点加1另外一个点减1,问最少操作多少次,能够让1, 2, .... n-1 这些位置的数
全部变成0,其实就是统计1, 2, .... n-1 这些位置的差分序列中正数和负数的和,每次
操作优先选一个正数,一个负数,正数做减法,负数做加法,只剩正数或者只剩负数时候,
要么和0位置的数配对操作,要么和n位置数配对操作,虽少操作次数就是 min(sum1, sum2) + abs(sum1-sum2) = max(sum1, sum2)
最后剩余的整数绝对值和或者负数绝对值和是abs(sum1, sum2), 0位置被配对操作侧次数可能是
0, 1, 2, ..... abs(sum1, sum2), 因此最终差分序列第一项可能有abs(sum1 - sum2)+1种选择
也就是最终序列的状态有abs(sum1 - sum2)+1种可能
'''
n = int(input())
S = int(input()) # 当前差分序列的最后一项
last_val = S
pos_sum, neg_sum = 0, 0 # 差分序列中正数和负数的绝对值的和
for i in range(1, n):
val = int(input())
S, last_val = val - last_val, val
if S > 0:
pos_sum += S
elif S < 0:
neg_sum -= S
print(max(pos_sum, neg_sum))
print(abs(pos_sum - neg_sum)+1)
print(abs(pos_sum - neg_sum)+1) 为啥子要加+1啊