AcWing 2074. 倒计数 模拟

题目描述

https://www.acwing.com/problem/content/description/2076/
题目大致意思是有$T$组序列，每组序列长度不同，每次会给出长度，同时给出一个数$K$，让你找出每个序列中有多少个连续的$[K,k-1,k-2,...,1]$。
题目不难，直接模拟就行，下面看我代码思路。

---

代码

#include<iostream>
using namespace std;
const int N=2e5+10;
int num[N];
int t,n,k;
int main()
{
    
    scanf("%d",&t);
    int cnt=1;  //记录组别编号，从1开始
    while(t--)
    {
    
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++) scanf("%d",&num[i]);
        
        int count=0,i,j;
        for(i=0;i<n;)
        {
    
            if(num[i]==k)   //在序列中找到一个数等于k
            {
    
                if(n-i<k) break;//此时如果剩余的序列长度小于k，那直接不用再找了，不会再有符合条件的
                //判断是不是倒计数
                bool flag=true;
                for(j=i;j<=i+k-1;j++)  
                    if(num[j]!=k-(j-i))
                    {
    
                        flag=false;
                        break;
                    }
                if(flag)  //是倒计数
                {
    
                    count++;
                    i=i+k-1+1;   //把i更新到倒计数的下一个
                }
                else   //不是倒计数
                    i=j;   //把i更新到第一个不符合的情况
            }
            else
                i++;
        }
        printf("Case #%d: %d\n",cnt++,count);
    }
    return 0;
}

---