增减序列
题目 增减序列
思路分析
需要对差分有比较深入的理解
要让原数组全一样 那就意味着要让差分数组从第二项开始全为0 这个能理解吧（b[1]=a[1]）
用贪心的思想，来使得b中所有数变成零
显然做b[L]++,b[R+1]--;操作的时候 找两个数配对 负数++ 正数-- 两两相消变0
此时的操作总次数为 min(pos,neg) 其中pos为差分数组中正数和 neg为负数和
但是最终结果可能依然不是全 0的，因为 abs(sum(正数))可能！=abs(sum(负数))
在经过上面的操作后 如果还有剩下 就一定剩下了同符号的数
怎么把这些同符号的数消掉
只能通过b[1]或者b[n+1]这两个对差分数组没有影响的数 来一个一个的把自己减为0
所以操作次数为个数的总和，abs(pos-neg);
综上 最少操作次数—— min(pos,neg) + abs(pos-neg)
还有一个问题 问有多少种结果
很容易知道 数列的值就是b[1]的值，根据逆推，原数组(也就是我们的数列)是差分数组的前缀和
根据前缀和的公式，s[i] = s[i-1] + b[i]
由于b[2]-b[n]都为0，故s[i] = s[i-1] = b[1]
所以我们对b[1]的操作次数也就是种类数量
由于贪心的去操作，一开始是对负数和正数两个点进行操作，所以b[1]没有变
之后数组就只剩下同符号的数
此时我们有两种方案
假设此时数组只剩下正数
方案一 b[1] += 1,b[i+1] -=1
方案二 b[i] -= (-1),b[n+1] += (-1)
因为最后的效果相同均是将2-n的数减为0，故两种方案均可
举例两个边界情况，如果只采取方案二，b[1]不变
如果只采取方案一，即需要操作abs(pos-neg)次，b[1] += abs(pos-neg);
假设一开始b[1]为2，abs(pos-neg)为3，b[1]的取值可能为2,3,4,5，即abs(pos-neg)+1
综上 结果数量—— abs(pos-neg)+1
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=1e5+10;
int b[N],a[N];
int n;
LL pos,neg;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
for(int i=2;i<=n;i++){
if(b[i]>0) pos+=b[i];
else neg-=b[i];
}
cout<<min(pos,neg)+abs(pos-neg)<<endl;
cout<<abs(pos-neg)+1<<endl;
return 0;
}
💬 评论