hdoj5806【尺取】

(补题,妈蛋那时候大哥给我说是尺取,我不想打…真是艾斯比了…)
题意:
退役狗 NanoApe 滚回去学文化课啦!

在数学课上,NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 n 的数列,他又根据心情写下了一个数 m。

他想知道这个数列中有多少个区间里的第 k 大的数不小于 m,当然首先这个区间必须至少要有 k个数啦。

思路:
首先就是大于m阿,然后,然后再去判断一下在区间内的大于m个的数有没有大于k,大于的话就保证这个区间包括后面所有都可以满足题目条件。。很水的尺取。。。
贴一发挫code…….

#include <iostream>
#include <cstdio>
#include<vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

const int N=2e5+10;
int a[N];
int s,e,cnt;
int n,m,k;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);

        LL ans=0;
        cnt=e=0;

        for(s=1;s<=n;s++)
        {
            while(cnt<k&&e<=n)
            {
                if(a[++e]>=m)
                    cnt++;
            }
            if(cnt>=k)
                ans+=n-e+1;
            if(a[s]>=m)
                --cnt;
        }
        printf("%lld
",ans);
    }
    return 0;
}

​​

原文地址:https://www.cnblogs.com/keyboarder-zsq/p/5934378.html