当我看到这题的时候立刻眼前一亮，觉得这是一个很经典的尺取法案例，我觉的好处就在于对初了解尺取法的训练，通过该题能检测到底是不是真正了解了尺取法，还有代码的熟练度。比赛嘛，时间是很珍贵滴 ok废话不多说
标题：日志统计
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：
ts id
表示在ts时刻编号id的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
【输入格式】
第一行包含三个整数N、D和K。
以下N行每行一条日志，包含两个整数ts和id。
对于50%的数据，1 <= K <= N <= 1000
对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
【输出格式】
按从小到大的顺序输出热帖id。每个id一行。
【输入样例】
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
【输出样例】
1
3
解题思路：截选在尺取，先截选id在尺取时间，借用内部类封装id和获赞时间，按照id排序；这些都是解题模子，想不到也没关系，多练习才是王道值得一提的由于题目的特殊性只要满足获赞数等于K当前就为热帖，该id就一定输出所以继续尺取下一个id就可以了，大大节约了时间也是题目100%数据通过测试的必要
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int D = sc.nextInt();
int K = sc.nextInt();
int[][] ts_id = new int [N][2];
for(int i = 0; i < N; i++) {
for(int j = 0; j < 2; j++) {//每行分别代表获赞时间和id
ts_id[i][j] = sc.nextInt();
}
}
Id_Ts[] id_Arr = new Id_Ts[N];
for(int i = 0; i < N; i++) {
id_Arr[i] = new Id_Ts(ts_id[i][0], ts_id[i][1]);
}
Arrays.sort(id_Arr);
solve(N, D, K, id_Arr);
}
/**
* 尺取法
* @param N
* @param D [x, x+D)
* @param K 获赞数
* @param id_Arr
*/
private static void solve(int N, int D, int K, Id_Ts[] id_Arr) {
if(N == 1) {
System.out.println(id_Arr[0].id);
return;
}
int left_id = 0;
int right_id = 1;
int l_ts = 0;
int r_ts = 0;
while(left_id < N) {
while(id_Arr[right_id].id == id_Arr[left_id].id) {
right_id++;
if(right_id >= N)
break;
}
right_id--;
l_ts = left_id;
r_ts = l_ts;
int tempK = 0;
while(l_ts <= right_id) {//尺取时间段
if(id_Arr[r_ts].ti - id_Arr[l_ts].ti < D) {
tempK++;
r_ts++;
if(r_ts > right_id&&tempK < K) {//不是热帖
break;
}else if(tempK >= K) {
System.out.println(id_Arr[left_id].id);
break;
}
}else {
l_ts++;
r_ts = l_ts;
tempK = 0;
}
}
right_id++;
left_id = right_id;
}
}
private static class Id_Ts implements Comparable<Id_Ts>{
int ti;
/**
* 获赞时间
*/
int id;
/**
* 获赞id
*/
@Override
public int compareTo(Id_Ts o) {//按id先后进行排序,id相等按获赞时间排序
if(this.id == o.id)
return this.ti - o.ti;
else
return this.id - o.id;
}
public Id_Ts(int ti, int id) {
super();
this.ti = ti;
this.id = id;
}
@Override
public String toString() {
return "Id_Ts [ti=" + ti + ", id=" + id + "]";
}
}
}
