Hdu 5806 NanoApe Loves Sequence Ⅱ(双指针)

Hdu 5806

题意：给出一个数组，求区间第k大的数大于等于m的区间个数

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

inline int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int N=2e5+10;

int a[N];

int main()

{

    int T=read();

    while(T--){

        int n=read(),m=read(),k=read();

        for(int i=0;i<n;i++) a[i]=read();

        int l=0,r=0,cnt=0;

        ll ans=0;

        while(l<=r&&r<n){

            while(r<n&&cnt<k){

                if(a[r++]>=m) cnt++;

            }

            if(r>n||cnt<k) break;

            if(cnt==k) ans+=n-r+1;

            while(cnt==k){

                if(a[l++]>=m) cnt--;

                if(cnt==k) ans+=n-r+1;

            }

        }

        printf("%lld\n",ans);

    }

    return 0;

}

Java版本实现，输入可能会导致超时，需要使用BufferedInputStream加速

import java.io.*;

import java.util.*;

class MyInputStream extends InputStream {

    public BufferedInputStream bis = new BufferedInputStream(System.in);

    public int read() throws IOException {

        int i;

        while ((i = bis.read()) < 48)

            if (i == -1)

                return -1;

        int temp = 0;

        while (i > 47) {

            temp = temp * 10 + i - 48;

            i = bis.read();

        }

        return temp;

    }

}

public class Main

{

	static final int N=200005;

	static int a[]=new int[N];

    public static void main(String[] args) throws IOException{

    	MyInputStream sc=new MyInputStream();

    	int T=sc.read();

    	Integer zero=new Integer("0");

        while(!zero.equals(T--)){

        	int n=sc.read(),m=sc.read(),k=sc.read();

        	for(int i=0;i<n;i++) a[i]=sc.read();

        	int l=0,r=0,cnt=0;

            long ans=0;

            while(l<=r&&r<n){

                while(r<n&&cnt<k){

                    if(a[r++]>=m) cnt++;

                }

                if(r>n||cnt<k) break;

                if(cnt==k) ans+=n-r+1;

                while(cnt==k){

                    if(a[l++]>=m) cnt--;

                    if(cnt==k) ans+=n-r+1;

                }

            }

            System.out.println(ans);

        }

    	sc.close();

    }

}