题目链接
题目大意：
给定一个长度为 (n) 的数列 { (a_1) , (a_2),(cdots),(a_n)} ，每次可以选择一个区间([l,r])，使这个区间内的数都加 (1) 或者都减 (1)。
请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
题目思路：
以下的解法可能不是最优，敬请留意。
这种序列题常常会用到前缀和/差分进行求解。由于本题要求最后数字相同，可以想到差分后为数组为0。考虑差分。
差分后数组中有正数，负数和0，题目转化为需使不为0的数变为0的操作数。当然，差分数组的第1和第n+1项除外，因为其跳跃出边界。
现在，题目中的加1操作变为将左端点(+1)，右端点(-1) ,减1操作则恰好相反。
那么，要使操作最小，我们可以猜测应该使操作两个影响点应尽量在非(1)和(n+1)的位置上，也就是都有效。剩余的则只能与(1)和(n+1)项配合完成。这个操作显然可以模拟。
当然，这个解法并不算优，如需更优欢迎移步Luogu
第一问可以解决了，现在考虑第二问：
我们将第一个数作为指标，考虑第一个数有多少变化可能。第一个数变化当且仅当操作涉及到第一个数，也就是无法与中间配对的操作（这些操作可以与(1)、(n+1)配对，是等价，可互换的）。再加上原来的一个即可。
上代码
#include<bits/stdc++.h>
using namespace std;
int n,a[100100],c[100100],qp[100100],qf[100100];
long long ans,sum;
int main()
{
cin>>n;
int hp=1,tp=0,hf=1,tf=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
c[i]=a[i]-a[i-1];
if (i==1) continue;
if (c[i]>0) qp[++tp]=i;
if (c[i]<0) qf[++tf]=i;
}
sum=1;
while (hp<=tp||hf<=tf)
{
int kp=qp[hp],kf=qf[hf];
if (hp>tp) c[kp]=2147483647;
if (hf>tf) c[kf]=-2147483647;//不能与2~n配对，那么有可能影响1
int v=min(c[kp],-c[kf]);
if (c[kp]==2147483647) sum+=-c[kf];
if (c[kf]==-2147483647) sum+=c[kp];
ans+=v;
//可配对情况
if (c[kp]>-c[kf])
{
c[kp]-=v;c[kf]+=v;
hf++;
}
else
{
if (c[kp]==-c[kf])
{
c[kp]-=v;c[kf]+=v;
hf++;hp++;
}
else
{
c[kp]-=v;c[kf]+=v;
hp++;
}
}
}
cout<<ans<<endl<<sum;
return 0;
}