Hdu 5806 NanoApe Loves Sequence Ⅱ(双指针)
题意：给出一个数组，求区间第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
",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();
}
}