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;
}
0 条评论