AcWing 100. 增减序列
原题链接
中等
作者:
汪宏睿
,
2023-08-06 23:37:14
,
所有人可见
,
阅读 68
/*
看到有操作给l-r的区间都+1/-1,非常自然地想到了差分
看看将这个题转化成差分,话发生什么事情
记原数组为a
差分数组为b
要求:除了b1以外,其余b值都必须为0,即使得b2~bn都为0,我们把这个范围称为有效操作范围
有操作可以将从b1~bn+1中任意挑两个不一样的数,前面的数+1/-1,后面的数-1/+1且与前一数不同
1.如果操作包含b1,那么实际上的效果只能给有效操作范围中的*一个*数-1/+1
2.如果操作包含bn+1,那么实际上的效果只能给有效操作序列范围中的*一个*数-1/+1且与前一数不同
3.那么如果同时包含b1和bn+1,那么实际上对有效操作范围没有任何改变,纯属徒劳
4.相反,如果不包含b1,bn+1,那么可以同时改变两个数,但是,需要有一个是负数,有一个是正数,如果两个数都是正或都为负,是无法进行这个操作的
因此,我们记录b数组中除了b1以外有整数之和为m和负数之和为-n,那么我们可以选择min(m,n)个数进行4操作,再将剩下的abs(m-n)个数进行2或1操作
那么其实,最少操作次数就是max(m,n);
以为剩下的abs(m-n)是或的关系,就会有不同的方案,由于m,n完全对称,所以有几个m就有几个对应的n,对于m有abs(m-n)+1种情况
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
int b[N];
int n;
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
int p=0,q=0;
for(int i=2;i<=n;i++)
{
if(b[i]<0) p-=b[i];
else if(b[i]>0) q+=b[i];
}
printf("%lld\n",max(p,q));
printf("%lld",abs(p-q)+1);
return 0;
}