差分 + 贪心
差分
- 让原数组中所有数都一样,体现在
差分数组
中,既:除了第一个数可以是任意值,之后的所有数都要为0
- 基于这个想法,利用对差分数组的操作。可以实现对
b2 ~ bn
中的某一个数 + 1
,对另一个数 - 1
的操作;或者是b1或bn+1 加一/减一
,对b2 ~ bn 中的某一个数 + 1 或 - 1
有了操作方法,现在需要知道怎么才能使操作次数最小
贪心
- 由于我们知道,
b1
可以是任意的值,所以重要的是我们要尽量多对b2 ~ bn
的数进行操作,所以我们优先采用第一种操作方法
- 在第一种操作方法中,是让
b2 ~ bn
中的一个数加,一个数减,在差分数组中,我们是要让b2 ~ bn
的数都变为0
,那肯定是让一个正数减,一个负数加才是最优解。 - 所以我们先让差分数组中的正负数在第一种操作方式下互相抵消(注意第一种操作方式的范围是
b2 ~ bn
,所以b1
的值不能被统计在内)。最后剩下的正数或者负数,就用第二种操作方式,对b1
和剩下的数进行操作,最终得到b1为任意值
,b2 ~ bn全为0
的结果
故!此题的答案就是:
最小操作数:第一种操作次数 + 第二种操作次数;
保证最小操作次数的情况下,可以得到的结果种数:第二种操作次数 + 1(ps:第二种操作方式可以改变b1
的值,b1
的原值也是一种情况,故 + 1
)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i ++)
{
scanf("%d",&a[i]);
b[i] = a[i] - a[i - 1];
}
long long sum_z = 0, sum_f = 0; //正数的和,负数的和
for(int i = 2;i <= n;i ++) //统计正数和负数和的时候,b1不计算在内,因为第一种操作方式的范围是b2 ~ bn
{
if(b[i] > 0) sum_z += b[i];
else sum_f -= b[i];
}
//第一种操作次数 : min(sum_z,sum_f)
//第二种操作次数 : abs(sum_z - sum_f)
//合起来就是max(sum_z,sum_f)
//可能得到的结果 + 1是因为,b1的原值也是一种结果
printf("%lld\n%lld",max(sum_z,sum_f),abs(sum_z - sum_f) + 1);
return 0;
}