题目链接：AcWing 1238. 日志统计
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N行。
其中每一行的格式是：ts id
表示在 ts时刻编号 id的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D的时间段内收到不少于 K个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 T满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K。
以下 N行每行一条日志，包含两个整数 ts 和 id。
输出格式
按从小到大的顺序输出热帖 id。
每个 id占一行。
数据范围
1≤K≤N≤105,
0≤ts,id≤105,
1≤D≤10000
输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例：
1
3
程序说明：
暴力做法是枚举时间段，可以用双指针优化。
代码如下：
import java.util.*;
import java.io.*;public class Main {
static int N = 100010;static int n, d, k;static Pair[] logs = new Pair[N];static boolean[] st = new boolean[N];static int[] cnt = new int[N];public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));n = sc.nextInt();d = sc.nextInt();k = sc.nextInt();for(int i = 0; i < n; i++) {
int a = sc.nextInt();int b = sc.nextInt();logs[i] = new Pair(a, b);}Arrays.sort(logs, 0, n);for(int i = 0, j = 0; i < n; i++) {
int id = logs[i].id;cnt[id]++;while(logs[i].time - logs[j].time >= d) {
cnt[logs[j].id]--;j++;} if(cnt[id] >= k) st[id] = true;}for(int i = 0; i < N; i++)if(st[i] == true)System.out.println(i);}
}
class Pair implements Comparable<Pair> {
int time, id;public Pair(int time, int id) {
this.time = time;this.id = id;}public int compareTo(Pair p) {
return this.time - p.time;}
}