洛谷刷题笔记——P4552 [Poetize6] IncDec Sequence

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$。

输出格式

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

思路

对于一个连续区间内的元素进行修改，可以考虑通过差分来实现。令差分数组为d[]，使数列中的所有数都一样，就是让差分数组除第一个元素外，其余元素均为$0$。

如果令原数组的区间$[l,r]$内的所有元素$+1$，则原数组对应的差分数组有：d[l] += 1, d[r+1] -= 1；同理，令原数组的区间$[l,r]$内的所有元素$-1$，则原数组对应的差分数组有：d[l] -= 1, d[r+1] += 1。特别地，如果对$l$号元素及后面的所有元素进行修改，则只需修改d[l]；如果对$r$号元素及前面的所有元素进行修改，则只需修改d[r+1]。

此时，我们注意到：对原数组的任意区间进行任意的$+1$、$-1$操作，都可以通过直接修改差分数组来实现，并且最终答案也与差分数组的一种状态相对应，所以接下来我们只需要关注差分数组即可！

首先解决第一个问题：如何用最少的操作使数列中所有元素相同？即让差分数组除第一个元素外，其余元素均为$0$。从上文可知，一次操作最多可以令差分数组中的两个元素发生改变，即让一个元素$+1$，让另一个元素$-1$，所以我们应该尽可能多地进行这种操作。那么，这种同时$+1$、$-1$的操作最多可以进行多少次呢？我们令pos为差分数组中所有正元素的绝对值之和，neg为所有负元素的绝对值之和，则同时$+1$、$-1$的操作最多可以进行min(pos, neg)次。上述操作完成后，我们就只能对差分数组中的单个元素进行修改，最少要修改abs(pos-neg)次。所以，答案为min(pos, neg)+abs(pos-neg)次，即max(pos, neg)次。

然后解决第二个问题：最终得到的数列有多少种？即d[0]有多少种取值？在解决第一个问题的过程中，我们进行了两类操作：一类是同时修改差分数组的两个元素，另一类是只修改差分数组的一个元素。我们考虑对后一类操作进行改造，比如：原操作为d[i]+1，现将其改为d[0]-1, d[i]+1。由于后一类操作要么全是$+1$，要么全是$-1$，所以每进行一次操作，d[0]都会得到一个新的值，再加上d[0]的初始值，可知d[0]最多有abs(pos-neg)+1种取值。

代码

#include
#define maxn 100005
#define int long long
using namespace std;

int n, mid;
int a[maxn], d[maxn];
int sum = 0;
int pos=0, neg=0;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	d[0] = a[0];
	for(int i=1;i<n;i++) d[i] = a[i]-a[i-1];
	for(int i=1;i<n;i++){
		if(d[i]>0) pos += d[i];
		else neg += -d[i];
	}
	cout<<max(pos, neg)<<'\n'<<abs(pos-neg)+1;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24