Luogu 4552 [Poetize6] IncDec Sequence

在BZOJ上好像被权限掉了。

考虑差分，定义差分数组$b$　　　　

　　$$b_i = \left\{\begin{matrix}
　　a_i \ \ \ (i == 1)\\ 　　
　　a_i - a_{i - 1}\ \ \ (i > 1)
　　\end{matrix}\right.$$

那么我们最后就是要使 $\forall i \in [2, n]\ \ b_i == 0$，并不关心$b_1$的取值。

差分之后区间修改变成了$+1$和$-1$的单点修改，如果要用最少的次数完成修改，那么肯定先要对所有$b_i > 0$的进行$-1$的操作，而$b_i < 0$得进行$+1$的操作，发现正负数可以两两配对，设$b_i$ $i \in [2, n]$中所有正数的和为$p$，所有负数的绝对值和为$q$，那么有$min(p, q)$次可以配对修改，还有$\left | p - q \right |$需要拎出来单独修改，那么第一问的答案就是$min(p, q) + \left | p - q \right | = max(p, q)$。

而第二问相当于求有多少个$b_1$，易得答案为$\left | p - q \right | + 1$。

时间复杂度$O(n)$。

注意开$long \ long$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e5 + ;

int n;

ll a[N], b[N], sumP = , sumN = ;

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

template <typename T>

inline T max(T x, T y) {

    return x > y ? x : y;

}

template <typename T>

inline T abs(T x) {

    return x >  ? x : -x;

}

int main() {

    read(n);

    for(int i = ; i <= n; i++) {

        read(a[i]);

        b[i] = a[i] - a[i - ];

        if(i == ) continue;

        if(b[i] < ) sumN -= b[i];

        if(b[i] > ) sumP += b[i];

    }

    printf("%lld\n%lld\n", max(sumN, sumP), abs(sumP - sumN) + 1LL);

    return ;

}

巴特西

Luogu 4552 [Poetize6] IncDec Sequence

最新文章

热门文章