P14524 [BYOI R1] 意识解离 题解

· · 题解

P14524 [BYOI R1] 意识解离

题目翻译

判断一个非负整数序列每项是否可以拆成任意个任意长度在结尾处对齐的正整数序列之和。

思路

先考虑特殊情况，发现当序列中有 0 时，无论如何也不能用正整数表示，可以直接特判。

然后贪心，会发现实现满足要求的操作实际上是将任意一位之后的所有数减一，而无法满足的条件就是在操作过程中，有元素的值小于等于零了。这样就会使前面的数实现递减前，后面的数显到达零从而无法再拆。具体请看代码：

代码

#include<bits/stdc++.h>
#define Xuanbo return 0
#define int long long
using namespace std;
const int N=1e6+6;
int T;
int n,x;
int a[N];
signed main(){
    for(cin>>T;T;T--){
        cin>>n;
        x=0;
        bool flag=1;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]==0)flag=0;
            if(i==1)continue;
            if(a[i]-x<=0)flag=0;
            if(a[i]>a[i-1])x++;
        }
        if(flag)cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }
    Xuanbo;
}