问题
给定一个长度为 n 的数列,每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
输入格式
第一行输入正整数n。
接下来n行,每行输入一个整数,第i+1行的整数代表 。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
0<n≤,
0≤<2147483648
输入样例:
4
1
1
2
2
输出样例:
1
2
思路
把序列A的区间 [l, r] 加d(即为把A[l],A[l+1],A[r]都加上d),其差分序列B只发生如下变化:
令B[n] = 0,加入到B中,则由本题可知,即为在B[i](0 <= i <= n)中,任选两项,一项加1,一项-1,最终使得B[i](1 <= i <= n-1)都变为0。则有如下3三种有效选法:
- 从 [1,n-1] 中选,则两项应该尽量保证一正一负(因为一项加一项减),以减少操作次数,更快接近目标;
- 一项选A[0],另一项在 [1,n-1] 中选;
- 一项选A[n],另一项在 [1,n-1] 中选;
设B[1]~B[n-1]中的正数和为p
,负数和的绝对值为q
。则首先用第一种选法,将正负数进行抵消,用去min(p,q)
次操作。剩余|p-q|
的数未配对,可以选择选法2或者3进行配对,消耗|p-q|
次操作。
则综上所述,最少操作次数为 。又根据|p-q|
次的第二或第三种操作,导致B[0]的数值有 种。
题解
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MAX = 100010;
int a[MAX]; //输入的原序列ai
int b[MAX]; //差分序列
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if (i == 0) b[i] = a[i];
else b[i] = a[i] - a[i - 1];
}
ll z = 0, nz = 0;
for (int i = 1; i < n; i++) {
if (b[i] > 0) z += b[i];
if (b[i] < 0) nz -= b[i];
}
cout << max(z, nz) << endl;
cout << abs(z - nz) + 1 << endl;
return 0;
}
标题: | AcWing-100-增减序列 |
---|---|
链接: | https://www.fightingok.cn/detail/39 |
更新: | 2022-09-18 22:33:30 |
版权: | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |