A10 差分 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P4552 ↗

题目描述

给定一个长度为 $n$ 的数列 ${a_1,a_2,\cdots,a_n}$ ，每次可以选择一个区间 $[l,r]$ ，使这个区间内的数都加 $1$ 或者都减 $1$ 。

请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

输入格式

第一行一个正整数 $n$
接下来 $n$ 行,每行一个整数,第 $i+1$ 行的整数表示 $a_i$ 。

输出格式

第一行输出最少操作次数
第二行输出最终能得到多少种结果

输入输出样例

输入 #1

plaintext

输出 #1

1
2

plaintext

对于 $100\%$ 的数据， $n\le 100000, 0 \le a_i \le 2^{31}$ 。

算法解析#

差分思想

把序列 $a$ 的区间 $[l,r]$ 加 $d$ ，等价于其差分序列 $b$ 的点 $b[l]$ 加 $d$ ，点 $b[r + 1]$ 减 $d$ ，其他位置不变。

即把原序列的“区间操作”转化为差分序列的“两点操作”。多次区间操作完成后，再利用前缀和还原。

时间复杂度从 $O(n^2)$ 降为 $O(n)$ 。

示例： $a$ : 1 2 3 1 2 3 $b$ : 1 1 1 -2 1 1

Python代码实现#


n = int(input())
a = [0]
b = [0] * (n + 1)
for i in range(1, n + 1):
    a.append(int(input()))
    b[i] = a[i] - a[i - 1]
p, q = 0, 0
for i in range(2, n + 1):
    if b[i] > 0:
        p += b[i]
    else:
        q += abs(b[i])
print(max(p, q))
print(abs(p - q) + 1)

python

C++代码实现#

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N=100010;
int a[N], b[N];

int main(){
  int n;
  cin>>n;
  for(int i=1; i<=n; i++) cin>>a[i];
  for(int i=1; i<=n; i++) b[i]=a[i]-a[i-1];

  LL p=0, q=0;
  for(int i=2; i<=n; i++)
    if(b[i]>0) p+=b[i];
    else q+=abs(b[i]);

  cout<<max(p,q)<<'\n'<<abs(p-q)+1;
}