CF1862C Flower City Fence

One_JuRuo · 2023-08-25 07:42:09 · 题解

思路

原题中已经告诉了我们一种快速判断的方法，我们可以用这个方法来判断。

观察一下横着摆的方式，第一列的高度为 a_i\ge 1 的个数，第二列的高度为 a_i\ge 2 的个数 \cdots。

所以我们只需要逐列判断两种方式的高度是否一样就行了。

因为题目中给定了数组 a 是单调不升的，所以我们可以用一个变量 j 存最后一个 a_j\ge i 的位置，下一次 i 变大了一，就循环找到下一个 j 的位置即可。

AC code

#include<bits/stdc++.h>
using namespace std;
int t,n,a[200005],j,flag;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n),j=n,flag=0;//记得j要赋初始值
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        for(int i=1;i<=n;++i)
        {
            while(a[j]<i) --j;//找到对应的j
            if(a[i]!=j){flag=1;break;}//如果不满足，则标记并break
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
}