CF1442A Extreme Subtraction

作者: MayFlyyh 分类: 其他 发布时间: 2020-11-11 13:57 ė 6 没有评论

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;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/695

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部