给定一个长度为 n 的数列 a1, a2, ..., an,每次可以选择一个区间 [l, r],使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

输入格式

第一行输入正整数 n。

接下来 n 行,每行输入一个整数,第 i+1 行的整数代表 ai。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

  • $0 < n ≤ 10^5$
  • $0 ≤ ai < 2^{31}$

输入样例

4
1
1
2
2

输出样例

1
2

题目分析

分析样例: 1 1 2 2

我们有两种最小增减结果: 1 1 1 1 2 2 2 2

我们可以获得 1 1 2 2 的差分数组 1 0 1 0。 可以发现,只要差分数组的第二位到最后一位都为0时,该序列的每个元素就完全相同。

根据上面的思路,我们可以先获得序列的差分数组。分别统计数组第二位之后的正数和eve和及负数和neg

最小的操作步骤即 max(eve, neg),能得到 abs(eve - neg) + 1种结果。

代码实现

#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;

ll n, arr[N], val, eve, neg;
inline void push(int l, int r, int val) {
    arr[l] += val, arr[r + 1] -= val;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> val;
        push(i, i, val);
    }
    for (int i = 1; i < n; ++i) {
        if (arr[i] < 0) neg -= arr[i];
        else eve += arr[i];
    }
    cout << max(eve, neg) << '\n' << abs(eve - neg) + 1 << endl;;

    return 0;
} 
分类: PrefixSum

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status