CF1474D Cleaning 题解

linjunye · 2025-09-05 17:47:47 · 题解

应该是简单一点的做法。

我们先假设一次操作是选择 i 和 i+1 并进行减一。

我们定义第 i 个数的操作次数为选择 i 和 i+1 进行减一，注意不包含选择 i-1 和 i 的。

那么，我们发现，第一个数的操作次数为 a_1，第二个就是 a_2-a_1，第三个则是 a_1-a_2+a_3，以此类推。

我们定义 s_i 为这个式子，那么我们要满足 s_i\ge 0 才行。

这样不太优雅，我们可以将是偶数的 i 的 s_i 取反，这样就有了一个统一的格式：s_i=a_1+a_3+a_5+\cdots-a_2-a_4-\cdots。

那么，我们的限制要改变一下：对于 i 是奇数，s_i\ge 0；对于 i 是偶数，s_i\le 0。

注意有一种情况，就是第 n 堆还没有取完。这个时候我们可以新建一个堆 n+1，里面放有 0 个石子，就可以解决了。

这样你就会 O(n) 的判断了。

接下来看一次交换会改变什么。

注意，下面默认 n 为新建完一堆石子后的堆数（即 n 你可以理解成 n+1）。

假设我们交换 i 和 i+1。

那么 s_i 会变成 s_{i-1}+a_{i+1} 或者 s_{i-1}-a_{i+1}，这个具体看 i 的奇偶性。

然后对于 i<j\le n，我们有变化量：当 i 是奇数时，变化量为 2\times a_{i+1}-2\times a_i；当 i 是偶数时，变化量为 2\times a_{i}-2\times a_{i+1}。

我们可以预处理出 L_j 和 R_j，分别表示能让 s_i 符合要求，最小能加的数和最大能加的数。

这个不难 O(n) 预处理。

我们发现，对于变化量 d，我们是不是只需要 L_j\le d\le R_j 就可以了？

不难发现限制其实就是：\max_{j=i+1}^{n}L_j\le d\le \min_{j=i+1}^{n}R_j。

这启发我们倒着做，后缀最值是不难做的。

然后有一个细节特判一下：如果存在一个 j，满足 j<i 并且 s_j 不符合要求，我们的交换是无意义的（因为还是不合法情况）。

这样，我们就做完了，代码量适中，细节有点多。

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=1000010;
const int INF=0x3f3f3f3f3f3f3f3f;
int n;
int a[N];
int s[N];
int l[N],r[N];
int flag[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    n++;//新增一堆
    a[n]=0;
    for(int i=1;i<=n;i++){
        s[i]=s[i-1];
        if(i%2==1)s[i]+=a[i];
        else s[i]-=a[i];
    }
    bool fl=1;
    for(int i=1;i<=n;i++){
        if(i%2==1)fl&=(s[i]>=0);
        else fl&=(s[i]<=0);
        if(i%2==1&&s[i]<0||i%2==0&&s[i]>0)flag[i]=0;//不合法
        else flag[i]=1;//合法
    }
    for(int i=1;i<=n;i++)flag[i]+=flag[i-1];//合法的数量
    if(fl){//都合法（也可以 if(flag[n]==n)）
        cout<<"YES\n";
        return;
    }
    for(int i=1;i<=n;i++){//INF 指无限大，-INF 指无限小
        if(i%2==1){
            if(s[i]<0)l[i]=-s[i],r[i]=INF;
            else l[i]=-s[i],r[i]=INF;
        }
        else{
            if(s[i]>0)l[i]=-INF,r[i]=-s[i];
            else l[i]=-INF,r[i]=-s[i];
        }
    }
    int L=max(l[n-1],l[n]),R=min(r[n-1],r[n]);
    for(int i=n-2;i>=1;i--){
        int val=s[i-1];
        if(i%2==0)val-=a[i+1];
        else val+=a[i+1];
        if(i%2==1&&val<0||i%2==0&&val>0){//这里就不合法
            R=min(R,r[i]);
            L=max(L,l[i]);
            continue;
        }
        if(L>R)break;//不可能存在L<=d<=R
        if(flag[i-1]!=i-1){
            R=min(R,r[i]);
            L=max(L,l[i]);
            continue;
        }
        int delta;
        if(i%2==0)delta=2*a[i]-2*a[i+1];
        else delta=2*a[i+1]-2*a[i];
        // cerr<<i<<"\n";
        // cerr<<L<<" "<<R<<"\n";
        // cout<<delta<<"\n";
        if(L<=delta&&delta<=R){//合法
            cout<<"YES\n";
            return;
        }
        R=min(R,r[i]);
        L=max(L,l[i]);
    }
    cout<<"NO\n";
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int Tc=1;
    cin>>Tc;
    while(Tc--)solve();
    return 0;
}
/*
a[1]>=0
a[1]-a[2]<=0
a[1]+a[3]-a[2]>=0
a[1]+a[3]-a[2]-a[4]<=0
a[1]+a[3]+a[5]-a[2]-a[4]<=0

相邻？
a[1]>=0
a[1]-a[3]<=0
a[1]+a[2]-a[3]>=0
a[1]+a[2]-a[3]-a[4]<=0
a[1]+a[2]+a[5]-a[3]-a[4]<=0

delta?
对于>i的下标
i%2==0:
delta=-(a[i+1]-a[i])+(a[i]-a[i+1])=-a[i+1]+a[i]+a[i]-a[i+1]=2a[i]-2a[i+1]
i%2==1:
delta=-(a[i]-a[i+1])+(a[i+1]-a[i])=-a[i]+a[i+1]+a[i+1]-a[i]=2a[i+1]-2a[i]

*/