HDU_5806

思路

机智题，自创双指针发同向扫描。
将不小于mm的数看作1，剩下的数看作0，那么只要区间内1的个数不小于k则可行，枚举左端点，右端点可以通过two-pointer求出。
时间复杂度O(n)。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define ll long long
ll a[200005],m,k,n;
bool b[200005];
int main(){
    int T;
    for(cin>>T;T--;){
        memset(b,0,sizeof(b));
        scanf("%I64d%I64d%I64d",&n,&m,&k);
        for(int i=1; i<= n ;i++){
            scanf("%I64d",&a[i]);
            if(a[i]>=m)b[i]=1;
        }
        ll i=1,j=k,cnt=0;
        ll ans=0;
        for(int i=1; i<=k ; i++)
            if(b[i])cnt++;
        while(j<=n){
            while(cnt<k && j<=n){
                if(b[++j])cnt++;
            }
            ans+=n-j+1;
            if(b[i])cnt--;
            i++;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}