IncDec Sequence

题目大意：给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

数据范围：对于100%的数据，n=100000，0<=ai<2147483648

题解：

首先，对于这种操作是区间加啊区间减啊的题，不难想到差分。

现在假设，$b_i = a_i - a_{i - 1}$，$b$序列有$n$个值。

我们要保证对于$2\le i\le n$，$b_i == 0$且操作次数最小。

现在假设，$b_2$到$b_n$中，所有正数的和是$S1$，所有负数的绝对值的和是$S_2$。

因为我们不用管$b_1$，所以我们就相当于有两种操作：

一种是$S1--$且$S1--$。

一种是$S1--$或$S2--$。

那么最小的操作次数显然就是$max(S1, S2)$。

最终的序列个数呢？

现在，每一种最终的差分序列都对应原序列，那么原序列个数就等于$b_1$的取值个数。

发现只有一种.......

这是为什么呢？？？

看看样例就发现了端倪：

我们发现，两种操作的第二种，是可以使得$b_1$的值不变，但是仍然挑一个$S$令其$-1$。

这就相当于对区间$[i, n]$实施操作。

故此呢，我们还需要弄一个$b_{n +1}$表示$-a_n$。

这样的话，每次二操作都是从$b_1$和$b_{n + 1}$中选一个$-1$。

一共有$max(S1,S2)-min(S1,S2)$次二操作的机会。

只需要分成两边就好，所以最终的序列一共有$max(S1,S2)-min(S1,S2) + 1$种。

代码：

#include <bits/stdc++.h>

#define N 100010 

using namespace std;

int a[N], b[N];

typedef long long ll;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

    int x = 0, f = 1;

    char c = nc();

    while (c < 48) {

        if (c == '-')

            f = -1;

        c = nc();

    }

    while (c > 47) {

        x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

    }

    return x * f;

}

int main() {

    int n = rd();

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

        a[i] = rd();

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

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

    }

    ll S1 = 0, S2 = 0;

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

        if(b[i] < 0) {

            S2 -= b[i];

        }

        else {

            S1 += b[i];

        }

    }

    if(S1 < S2)

        swap(S1, S2);

    printf("%lld\n%lld\n", S1, S1 - S2 + 1);

    return 0;

}

小结：有的时候发现当前算法有些问题，但是有不知道哪里有问题，可以挑几组小数据玩一玩，会有收获的（确信。

巴特西

[bzoj3043]IncDec Sequence_差分

IncDec Sequence

最新文章

热门文章