【题解-Acwing】100. 增减序列

题目：100. 增减序列

题目描述

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

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

输入格式

第一行输入正整数 n。

接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 a_i。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

0 < n ≤ 10⁵ , 0 ≤ a_i < 2147483648

时空限制

1s / 64MB

输入样例

4
1
1
2
2

输出样例

1
2

思路（《算法进阶指南》）

本题目可以通过求a的差分序列b来求解，这样可以把对a序列的区间操作，转化为对b序列中两个值的操作。 b₁ = a₁，b_i = a_i – a_i-1（2 ≤ i ≤ n）。令b_n+1 = 0 题目转化为： 把b₂，b₃，…，b_n变为0，b₁为常数。

从b₁，b₂，…，b_n+1中任选两个数的方法可以分为四类：

设b₂，b₃，…，b_n中正数总和为p，负数总和的绝对值为q。 为了让操作次数最少，应该尽量执行第1类操作，可执行min(p, q)次。剩余|p – q|个未配对，每个执行第2或第3类操作，共需|p – q|次。 综上，最少操作次数为min(p, q) + |p – q| = max(p, q)次。根据 |p – q|次第2、3类操作的选择，能产生 |p – q| + 1种不同的b1值，即最终得到的序列a可能有|p – q| + 1种。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, b[N];
LL p, q; //p为b数组正数之和,q为b数组负数之和

void insert(int l, int r, int c){
b[l] += c;
b[r + 1] -=c;
}

int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
int c;
cin >> c;
insert(i, i, c);

if(i > 1){
if(b[i] > 0) p += b[i];
else q -= b[i];
}

}

cout << min(p, q) + abs(p – q) << endl;
cout << abs(p – q) + 1;
return 0;
}

结果