摘要
Title: 100. 增减序列
Tag: 差分
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

100. 增减序列

题意

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

思路

当对数组进行差分处理时，可以发现差分数组有正有负，问题就转化了
从对一个区间进行+1-1操作，变成了对一个正数和一个负数进行-1+1的操作

即每次选两点i, j进行操作

• $2 \le i, j \le n$ 尽量选择第一种操作

• $i == 1, 2 \le j \le n$ 改前缀

• $2 \le i \le n, j == n + 1$ 改后缀

  所以

• 操作数，就是正数和负数和的最小值，加上两者的差的绝对值（因为如果哪一方多，就得通过2，3种修改方法），其实也就是 两者的最大值

• 方案数，就看2，3种修改方法，每个执行两者的差的绝对值各多少次

代码

'''
Author: NEFU AB-IN
Date: 2022-02-15 16:16:56
FilePath: \ACM\Acwing\100.py
LastEditTime: 2022-02-15 17:12:00
'''
N = int(1e5 + 100)
a = [0] * N
b = [0] * N

if __name__ == "__main__":
    n = int(input())
    neg = 0
    pos = 0
    for i in range(1, n + 1):
        a[i] = int(input())
    for i in range(2, n + 1):
        if a[i] - a[i - 1] > 0:
            pos += (a[i] - a[i - 1])
        else:
            neg -= (a[i] - a[i - 1])
    print(min(pos, neg) + abs(pos - neg)) # max(pos, neg)
    print(abs(pos - neg) + 1)