给定一个长度为 n的数列 a 1,a 2,…,a n,每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。 求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

输入格式

第一行一个正整数n。 接下来n行,每行一个整数,第i+1行的整数表示 a i 。

输出格式

第一行输出最少操作次数。 第二行输出最终能得到多少种结果。

输入样例:

4
1
1
2
2

输出样例:

1
2

数据范围: 对于10 0 ≤ ai < 2147483648

题目分析

对于这道题, 我们需要对区间进行操作。可以考虑使用差分算法将区间操作转换为点操作。 对于输入的数据,我们可以得到差分数组。 我们可以发现, 对于下标从 1 开始的差分数组,要使原数组中元素值都相同,需要 a[2~N] 为 0, 并且a[i]的值即整个数组相同的值。 考虑对区间进行操作,那么我们在差分数组中就需要对 a[i], a[j] 进行操作(其中一个增加,另外一个减小)。

  • i == j (对某一点进行操作)
  • i == 1 && j >= 2 && j <= n (改变区间)
  • 2 <= i, j <= n (改变区间) 我们可以发现 2 <= i, j <= n 是最贪心的(差分数组可能会出现正负抵消), 其次是 i == 1 && j >= 2 && j <= ni == j

那么我们可以取得区间(2~N)中的正值和负值。 操作的最小次数为: min(正值, abs(负值)) + abs(正值 - abs(负值)) = max(正值, abs(负值)) 可能的情况(a[1]的可能取值):abs(正值 - abs(负值) + (当前)

代码实现

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

long long n, num, a[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> num;
        a[i] += num, a[i + 1] -= num;
    }
    LL ne = 0, po = 0;
    for(int i = 2; i <= n; ++i) {
        if(a[i] > 0) po += a[i];
        else ne -= a[i];
    }
    cout << min(po, ne) + abs(po - ne) << '\n' << abs(po - ne) + 1;
}

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status