网站建设技巧饣金手指排名27,威县网站建设,wordpress安全,建设公司网站大概需要多少钱title: IncDec序列 date: 2023-12-14 21:10:36 tags: 差分 categories: 算法进阶指南 —传送门
题目大意 解题思路 区间操作#xff0c;可以考虑差分。观察发现#xff0c;最终变成相同的数#xff0c;相当于相邻的两个数之差为 0 0 0#xff0c;因此我们使用差分。先…
title: IncDec序列 date: 2023-12-14 21:10:36 tags: 差分 categories: 算法进阶指南 —传送门
题目大意 解题思路 区间操作可以考虑差分。观察发现最终变成相同的数相当于相邻的两个数之差为 0 0 0因此我们使用差分。先求出差分数组 b b b,分别统计正数和负数的大小。我们有四种操作 b i b_i bi 和 b j b_j bj会改变 ( i , j ) (i,j) (i,j) 内的大小 b 1 b_1 b1 和 b j b_j bj会改变 ( 1 , j ) (1,j) (1,j) 内的大小 b j b_j bj 和 b n 1 b_{n 1} bn1会改变 ( j , n 1 ) (j,n 1) (j,n1) 内的大小 b 1 b_1 b1 和 b n 1 b_{n 1} bn1 会改变整个数列的大小 可以肯定的是第四种是无用功操作是不会改变相对大小为了让相对大小尽可能的改变我们最优先才去第一种操作在一定 区间内 的大小相同的时候就考虑左端点和右边界的差值以及右端点和左边界的差值进行 2 、 3 2、3 2、3 操作。 统计可以得出最小的操作次数为 m i n ( z , f ) ∣ z − f ∣ min(z,f) \vert z - f\vert min(z,f)∣z−f∣其中 f f f 为负数的绝对值。 能产生 ∣ z − f ∣ \vert z - f\vert ∣z−f∣ 1 中不同的 b 1 b_1 b1结果即方案数。 代码实现
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;const int N 6E5 10, mod 1e9 7;int main()
{int n; cin n;vectorint 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;
}
