首页 > 代码库 > bzoj3043 IncDec Sequence

bzoj3043 IncDec Sequence

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3043

【题解】

比较神奇的一道题,开始没往差分的角度上想,所以没想出来。

考虑查分数组,有$n-1$个数,那么操作变成一个地方+1,一个地方-1.

显然最后是要让差分数组全部变成0. 设差分后所有正数的和为$cnt_a$,负数的绝对值和为$cnt_b$。

为了方便说明,我们在数组前和数组后分别增加一个虚拟差分位置。这两个位置的数是可以是任意的。

那么如果$cnt_a \not= cnt_b$,那么多出来的部分有2种选择:①跟数组前的虚拟差分位置进行操作;②跟数组后的虚拟差分位置进行操作。

由于最后剩下的一定是同一种符号的(要么正、要么负),所以只需要枚举前/后进行了多少次就行了,所以总方案是$|cnt_a - cnt_b| + 1$。

技术分享
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

# define abs(x) ((x) > 0 ? (x) : -(x))

int n, a[M];
ll cnta, cntb;

int main() {
    cin >> n;
    for (int i=1; i<=n; ++i) scanf("%d", a+i);
    for (int i=1; i<n; ++i) a[i] = a[i+1] - a[i];
    for (int i=1; i<n; ++i) if(a[i] >= 0) cnta += a[i]; else cntb -= a[i];
    cout << max(cnta, cntb) << endl << abs(cnta - cntb) + 1 << endl;
    return 0;
}
View Code

 

bzoj3043 IncDec Sequence