题目描述
blablabla
样例
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define N 100010
using namespace std;
long a[N]; //原序列,下标从1开始
long b[N]; //差分序列,下标从1开始
int main()
{
int i,n;
long pos=0,neg=0;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
b[1]=a[1];
for(i=2;i<=n;i++)
{
b[i]=a[i]-a[i-1];
}
b[n+1]=0; //初始a[n+1]=a[n]
//要想使a[i]转化成常数列,实际上就是使b1=a1,b2~bn=0,bn+1是什么无所谓
for(i=2;i<=n;i++)
{
if(b[i]>0)
{
pos+=b[i]; //计算差分序列b2~bn中正数的和
}
else
{
neg+=b[i]; //计算差分序列中b2~bn中非正数的和,结果要加绝对值
}
}
neg=abs(neg);
//pos和neg中的小者就是bi和bj一正一负配对时-1+1操作的数量
//剩余的|pos-neg|就是落单的差分序列中的正数或负数bk,这些差分序列剩余的正数或负数bk可以通过与差分序列中b1或
//bn+1进行+1-1操作使bk逐步变到0,而这些bk如果与b1配对进行+1-1的操作则会影响常数列的初值a1,从而影响最终
//的常数列。所以常数列的最多可能有|p-q|+1种(算上前面min(neg,pos)次不影响常数列初值的操作),最少可能有
//1种,就是差分序列中剩余的bk都与bn+1配对进行+1-1的操作
cout<<max(pos,neg)<<endl;
cout<<abs(pos-neg)+1<<endl;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla