IncDec序列

title: IncDec序列
date: 2023-12-14 21:10:36
tags: 差分
categories: 算法进阶指南

—>传送门

题目大意

解题思路

区间操作，可以考虑差分。观察发现，最终变成相同的数，相当于相邻的两个数之差为 $0$，因此我们使用差分。先求出差分数组 $b$,分别统计正数和负数的大小。我们有四种操作：

1. $b_i$ 和 $b_j$，会改变 $(i,j)$ 内的大小
2. $b_1$ 和 $b_j$，会改变 $(1,j)$ 内的大小
3. $b_j$ 和 $b_{n+1}$，会改变 $(j,n+1)$ 内的大小
4. $b_1$ 和 $b_{n+1}$ ，会改变整个数列的大小

可以肯定的是，第四种是无用功，操作是不会改变相对大小，为了让相对大小尽可能的改变，我们最优先才去第一种操作，在一定 区间内 的大小相同的时候，就考虑左端点和右边界的差值以及右端点和左边界的差值，进行 $2、3$ 操作。
统计可以得出，最小的操作次数为 $min(z,f)+|z?f|$，其中 $f$ 为负数的绝对值。
能产生 $|z?f|$ + 1 中不同的 $b_1$结果，即方案数。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 6E5 + 10, mod = 1e9 + 7;

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

	ll z = 0, f = 0;
	for(int i = 2; i <= n; i ++){
	    if(b[i] > 0) z += b[i];
	    else f += b[i];;
	}
	f = -f;;
	cout << max(z,f) << endl << abs(z - f) + 1 << endl; 
    return 0;
}