AcWing 100. 增减序列
原题链接
中等
作者:
江上舟摇
,
2023-02-13 21:06:28
,
所有人可见
,
阅读 121
//差分的性质运用和基本思维
//差分就不多说了基本操作
//题目要求得到的数都一样的最小操作次数,我们在求出差分数组之后可以进行如下操作
//因为我们最终目的是使得cf[2]~cf[N+1]都是0,a[1]=cf[1]
//所以说第一步肯定是尽量中和差分数组中的正负数,这种的是2<=i,j<=n
//第二种操作是修改a[i]的前缀,即i=1,2<=j<=n,就是让cf[1]+1,cf[j]-=1,那他只能让修改差分数组cf[j]一个数而已
//第三种操作是修改a[i]的后缀,即2<=i<=n,j=n+1,同上,也只能修改cf[i]种的一个数而已
//第四种是修改a[i]全部,即i=1,j=n+1这种没有操作意义所以说不要选这种操纵
//因此,现在的核心想法就是如何运用上述的三种操作,可以更快用更少的操作取完成我们的目标。从直觉上看,我们应该多用第一种操作,
//因为第一种操作它一次可以改变差分数组的两个数,而第二、三种操作,它一次只能改变差分数组中的一个数。
//那就很明确了,正数和负数中和需要min(zs,fs)次,还剩下abs(zs-fs)次,剩下的这些既可以与cf[1]配对
//也可以与cf[n+1]配对,即执行操作二三来修改他们,因此总次数是min(zs,fs)+abs(zs-fs)=max(zs,fs)
//至于产生序列的种数,我们知道,修改后序列的种数很明显是由cf[1]决定的,还剩下的abs(zs-fs)中,既可以与cf[1]配对
//也可以与cf[n+1]配对,那么cf[1]就可以分配0,1,2.....abs(zs-fs)个,同理cf[n+1]可分配abs(zs-fs),......1,0个,即操作二我们会修改
//cf[1]的值,如果我们进行abs(zs-fs)+1个不同的序列次操作二,就会有abs(zs-fs)+1个不同的序列
//所以说综上所述要达到所有数都相等的总次数是min(zs,fs)+abs(zs-fs)=max(zs,fs)
//产生不同的序列的种数是abs(zs-fs)+1个
//作者:江上舟摇
//链接:https://www.acwing.com/activity/content/code/content/5193656/
//来源:AcWing
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e5+10;
int n,a[N];
int zs,fs;
int cf[N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],cf[i]=a[i]-a[i-1];
for(int i=2;i<=n;i++)
{
if(cf[i]>=0) zs+=cf[i];
else fs-=cf[i];
}
cout<<max(zs,fs)<<endl;
cout<<abs(zs-fs)+1<<endl;
return 0;
}