小明维护着一个程序员论坛。现在他收集了一份”点赞”日志,日志共有 N� 行。
其中每一行的格式是:
ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞,小明就认为这个帖子曾是”热帖”。
具体来说,如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是”热帖”。
给定日志,请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K
以下 N�行每行一条日志,包含两个整数 ts和 id。
输出格式
按从小到大的顺序输出热帖 id
每个 id 占一行。
数据范围
1≤K≤N≤1051≤105,
0≤ts,id≤1050≤,≤105,
1≤D≤100001≤≤10000
输入样例:
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例:
1
3
思路:
因为统计一定时间内是否有效,因此我们首先按照时间顺序将输入序列排序。我们使用数组id记录每个id的帖子被点赞的次数,当次数大于k时,我们将相对应的t数组下标元素改变为true,说明该id的帖子达到要求。
但是我们在考虑次数时还要考虑时间的连续性。这也是我们使用双指针的原因,维护一个区间使得该区间内的时间维持在d时间中。如果超出,我们就需要对超出部分元素的次数减1(这里可能不好理解,这个-1能进行是因为这个区间是从前向后遍历的,并且已经按照时间顺序排序。如果之前有元素超出了并且已经>=k,我们-1后不影响t数组的结果。也就是说只保留局部结果)同时将j++
代码:
package lanqiao;
import java.util.*;
public class Main{
public static void main(String[] args) {
int[] id = new int[100000];
boolean[] t = new boolean[100000];
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int d = sc.nextInt();
int k = sc.nextInt();
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
int i1 = sc.nextInt();
int i2 = sc.nextInt();
arr[i] = new int[]{i1,i2};
}
sc.close();
Arrays.sort(arr,(a,b) -> (a[0] - b[0]));
List<Integer> ans = new ArrayList<>();
for (int i = 0, j =0; i < n; i++) {
id[arr[i][1]]++;
while(arr[i][0] - arr[j][0] >= d){
id[arr[j][1]]--;
j++;
}
if(id[arr[i][1]] >= k) t[arr[i][1]] = true;
}
for (int i = 0; i < t.length; i++) {
if(t[i]) System.out.println(i);
}
}
}