CF1253A Single Push 题解

lmndiscyhyzdxss · 2023-03-24 14:04:28 · 题解

题目大意

给出一个操作:在 1 \thicksim n 中选出两个数 l , r(1 \leq l \leq r \leq n) 在 l \thicksim r 这个区间里,每个数加上 k(k>0) 给定两个数组 a[1...n] 和 b[1...n] 求再一次操作后能否使数组 a 等于数组 b
例如: a=[3 , 7 , 1 , 4 , 1 , 2 ] , b=[3 , 7 , 3 , 6 , 3 , 2] 要使数组 a 等于数组 b ,需选择 l=3 , r=5 , k=2

题目分析

这道题首先想到的是暴力枚举 , 是指针一个指向数组 a ,一个指向数组 b ,分别做差,但时间复杂度为 \left(n^2\right)
我们可以用数组 a 与数组 b 做差,得到 c 数组,然后用一种类似尺取法的方法进行一个一个判断
正确的情况应该是: \begin{matrix}\underbrace{0,0,0\cdots0}\\l-1\end{matrix} $ $ \begin{matrix}\underbrace{h,h,h\cdots h}\\ l \thicksim r \end{matrix} $ $ \begin{matrix}\underbrace{0,0,0\cdots0}\\r+1\end{matrix}
我们要做什么事呢：
- 判断是否为负数,因为零不行
- 判断是否当前还是 0 或跟上一个一样,这样可以
- 储存第一个不是 0 的数
- 输出
  我构造了一个前缀和数组 , 可以快速判断后面是否都是零,不用三个循环了不像前面两位大佬们那么麻烦了，代码比较精炼
  AC代码
```
#include<bits/stdc++.h>
using namespace std;
int t,n,a[100010],b[100010],c[100010],d[100010],l,p;
int main()
{
cin>>t;
while(t--)
{
scanf("%d",&n),p=1,l=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),d[i]=0;
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++)c[i]=b[i]-a[i],d[i]=d[i-1]+c[i];
for(int i=1;i<=n;i++)
{
    if(c[i]<0){printf("NO\n");p=0;break;}//不可能加负数 
    else if(c[i]==0&&l==0||l!=c[i]&&c[i]==0&&d[n]-d[i]==0||l==c[i])continue;//如果当前还是0或跟上一个一样 
    else if(l==0&&c[i]!=0)l=c[i];//第一个不是0的数 
    else {printf("NO\n");p=0;break;}//否则不成立 
}
if(p==1)printf("YES\n");
}
return 0;
}
```

CF1253A Single Push 题解

题目大意

题目分析

AC代码