第一步对于学过差分的人应该不难想
定义差分数组 $dis quad s.t. quad dis[i] = a[i] - a[i-1] $
那么不难发现问题一只要让 (dis[2] ... dis[n])中全部为 (0) 即可
区间([l,r])加一操作在差分数组中意味着(dis[l]=dis[l]+1,dis[r+1]=dis[r+1]-1)
即在差分数组中每次选取((x,y),dis[x]=dis[x]+1,dis[y]=dis[y]-1)
注意这里(x,y)可以选取(1...n+1)
减一同理
最后要使(dis[2] ... dis[n])全为0,首先在(dis[2] ... dis[n])选取一个正数和一个负数是他们配对加一或减一,直到最后只剩下一个数,不难发现这个数就是(dis[2] ... dis[n])中正数的和(sum^+)和负数的和的绝对值(|sum^-|)的差,让他与dis[1]或dis[n+1]配对即可
最后整理可得:(min(sum^+,sum^-)+|sum^+-|sum^-||),即(max(sum^+,|sum^-|))就是第一小问答案
对于第二小问,不难注意答案序列的不同只和在第一小问中最后剩下的那个数(k = sum^+-|sum^-|+1)有关
我们这里不妨设(k > 0),那么它可以和1或n+1配对,这里两个操作就代表了原数组(a[1,k-1])全部加一和原数组(a[k,n])全部减一,也就产生了两种不同的序列
那么这两种操作进行的次数的和必然是(k),那么就产生了k+1中不同的选法(第一个操作进行(0...k)次)
对于(k < 0)的情况可以同样地进行讨论
那么第二问答案就是(k+1=|sum^+-|sum^-||+1)
//c++AC代码
#include <bits/stdc++.h>
using namespace std;
int n,a[(int)1e5+5],dis[(int)1e5+5];
long long sum_z,sum_f,rest;
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i)
{
scanf("%d",a+i);
}
for(int i = 1;i <= n;++i)
{
dis[i]=a[i]-a[i-1];
}
for(int i = 2;i <= n;++i)
{
if(dis[i] > 0)
sum_z+=dis[i];
else
sum_f+=dis[i];
}
rest=sum_z+sum_f;
printf("%lldn",max(sum_z,std::abs(sum_f)));
printf("%lld",(long long)std::abs(sum_z-std::abs(sum_f))+1);
return 0;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
