• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

AcWing100 IncDec Sequence

admin

11月 28, 2021

求出(a)的差分序列(b),其中(b_1 = a_1, b_2 = a_2 – a_1, … b_n = a_n – a_{n – 1})

根据题意以及公式可以发现,如果我们想让序列所有的数都一样,那么就是让(b_2, b_3, … b_n)所有的数全为(0),而(b_1 = a_1),即(b_1)决定着(a)的序列有多少种,其中让(a)序列发生变化,相当对(b_1, b_2, b_3, … b_{n + 1})任选两个数进行操作,那么有以下几种操作:

  1. 操作(b_i, b_j (2 leq i leq j leq n)),一加一减或者一减一加,用贪心的方面想这种操作可以更快地改变b序列地值,所以我们应该尽可能多的选这种操作。
  2. 操作(b_1, b_j \,\, (2 leq j leq n)),这样只能改变(b_2, b_3, … b_n)中地一个数。
  3. 操作(b_i, b_{n + 1}\,\,(2 leq i leq n)),与(2)同理。
  4. 操作(b_1, b_{n + 1}),相当于对整个序列(a)操作,没有什么意义。

综上,设(b)为正数的和为(p), (b)为负数的和为(q),对于目的(1):用尽可能少的操作使得序列(a)变成一样的数:
我们可以尽可能多的使用操作(1),然后再使用操作(2,3)都可以,那么答案就是:

[min(p, q) + |p – q| = max(p, q)
]

对于目的(2),因为(b_1 = a_1),所以说(b_1)的取值就是(a)序列的取值,所以说我们应该尽可能地使用操作(2)完成(|p – q|)所以说,答案就是:(|p – q| + 1)

#include <bits/stdc++.h>

using namespace std;

const int N = 1E5 + 10;
int n, a[N], b[N];

typedef long long LL;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1];

    LL p = 0, q = 0;
    for (int i = 2; i <= n; i++) {
        if (b[i] < 0) p += abs(b[i]);
        if (b[i] > 0) q += b[i];
    }

    cout << max(p, q) << endl << abs(p - q) + 1 << endl;

    return 0;
}

发表回复

您的电子邮箱地址不会被公开。