【滑动窗口】第九届蓝桥杯省赛B组：日志统计

 

 思路：区间最大长度为D，id和t配对后，按照时间排序，用双指针维护区间，这个区间长度最大长度不超过D。

cnt[id]记录当前区间id出现次数。

st[id]记录id是否为热帖。

只需要维护区间的右端点和左端点的情况。

参考ACWING梨绘小棠 的题解：

AcWing 1238. 日志统计 - AcWing

 

import java.util.*;
        import java.io.*;
        import java.math.*;
public class Main{
    static final int N=100010;
    static int n,d,k;
    static int[] cnt=new int[N];
    static boolean[] st=new boolean[N];
    static PII[] logs= new PII[N];
    public static void main(String[]args) throws IOException{
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[]s=br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        d=Integer.parseInt(s[1]);
        k=Integer.parseInt(s[2]);
        for(int i=0;i<n;i++){
            String[]str=br.readLine().split(" ");
            int t=Integer.parseInt(str[0]);
            int id=Integer.parseInt(str[1]);
            logs[i]=new PII(t,id);
        }
        Arrays.sort(logs,0,n);
        for(int i=0,j=0;i<n;i++){
            cnt[logs[i].id]++;
            while(logs[i].t-logs[j].t>=d){
                cnt[logs[j].id]--;
                j++;
            }
            if(cnt[logs[i].id]>=k)st[logs[i].id]=true;
        }
        for(int i=0;i<N;i++){
            if(st[i]==true)System.out.println(i);
        }
    }
}


class PII implements Comparable<PII>{
        int t,id;
        public PII(int t,int id){
            this.t=t;
            this.id=id;
        }
        public int compareTo(PII o){
            return Integer.compare(t,o.t);
        }
    }