CF1442A Extreme Subtraction

你有一个序列 a，你可以进行 2 种操作：

• 选择前 k 个数，将它们全部减 1

• 选择后 k 个数，将它们全部减 1

  k 由你自己定，并且每次操作可以不同。
  问是否可以把通过若干次操作整个序列变为全是 0 的序列

本题多测，有 t 组数据
t \le 30000 \sum n \le 30000 a_i \le {10}^6

如果可以全变成0，说明序列 a 可以拆成两个非负数列，一个单调不增（对应操作1），一个单调不减（对应操作2）

问题转化成能否构造出这两个数列，记为数列 p （单调不增）和数列 q （单调不减），

对于数列中的每个位置，都有如下关系
p_i\leq p_{i-1} \
q_i\geq q_{i-1} \
p_i+q_i=a_i
从第1个数开始构造，考虑到给后面的数留余地，尽量最优，令
p_1=a_1 \

q_1=0 \
那么对于第二个位置的数有 p_2=a_2-q_2
因为有 q_2\geq q_1

所以有 p_2 \leq a_2-q_1

因为还有 p_2\leq p_1\ ,

所以 p_2 直接取 min(a_2-q_1,p_1)

这样可以保证 p_2 在满足这两个不等式的同时尽量最大，为构造后面的数留有余地

然后 q_2=a_2-p_2 即可，此时 q_2 也尽量是最小的

如果 p_i<0 ，那么就说明不可能通过原题目中减法操作来达到，那么就不合法

#include<bits/stdc++.h>
const int N = 3e4+10;
int a[N],b[N],c[N],t,n;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        b[1]=0,c[1]=a[1];
        int fl=1;
        for(int i=2;i<=n;++i){
            c[i]=std::min(c[i-1],a[i]-b[i-1]);
            if(c[i]<0){
                fl=0;
                break;
            }
            b[i]=a[i]-c[i];
        }
        printf(fl?"YES\n":"NO\n");
    }
    return 0;
}