IncDecSequence

Posted on In

题目大意：对于给定序列，每次可以选取一段区间进行统一的加一或者减一，Q1最少操作多少次可以使得整个序列数字统一。Q2最终可以得到多少种结果。

对于区间操作，容易想到差分

所以我们就可以把问题转化了，对于该序列的差分序列以及第\(c_{n+1}\)项，如何使得除了\(c_1\)之外的项全为0

对于每次的选取区间，我们可以发现无非三种有意义的做法

\(c_2\)至\(c_n\)，保证其一正一负的条件下，尽可能多的使用该方法

\(c_1\)与\(c_i\)

\(c_i\)与\(c_{i+1}\)

设\(c_2\)至\(c_n\)中正数和为p，负数和为q，通关正负配对的方式（也就是尽量用第一种方法）可以执行\(min(p,q)\)次

对于剩下的\(\left| p - q\right|\)个没有配对的，每一个可以选择与\(c_1\)或者\(c_{n+1}\)配对共需要\(\left| p-q \right|\)

所以最少需要操作\(max(p,q)\)次

然后考虑有多少种不同的合法序列

也就是来判断有多少个不同的\(b_1\)，有\(\left| p-q \right| + 1\)个不同的值

加1是因为其本身不变的话，也是一种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
 * By Youngore
 * Time:22.10.17
 */
#include <cstdio>
#include <map>
#include <cmath>
#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 66;

int a[N], c[N];
int num, tot;

inline int youngore()
{
    int n, i; scanf ("%lld", &n);
    for (i = 1; i <= n; ++ i) scanf ("%lld", &a[i]);
    for (i = 2; i <= n; ++ i)
    {
        c[i] = a[i] - a[i - 1];
        if (c[i] > 0) tot += c[i];
        else num -= c[i];
    }
    cout << max(tot, num) << '\n';
    cout << abs(tot-num) + 1;
    return 0;
}

int thestars = youngore();

signed main() {;}