日志统计(蓝桥杯每日一题)
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 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
C++
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int, int> PII; const int N = 100010; int n, d, k; int cnt[N]; PII logs[N]; // 存放每时刻的点赞情况 bool st[N]; // 记录每个帖子是否是热帖 int main() { scanf ("%d%d%d", &n, &d, &k); for (int i = 0; i < n; ++ i) scanf("%d%d", &logs[i].x, &logs[i].y); sort(logs, logs + n); for (int i = 0, j = 0; i < n; ++ i) { int id = logs[i].y; // 这个时刻这这个id被点赞了 cnt[id] ++; // 然后这个人对应的cnt++ while(logs[i].x - logs[j].x >= d) // 如果区间【j, i】长度大于等于d // 就需要把前面多余的区间的cnt-- { cnt[logs[j].y] --; // 把前面加了的再减回来 j ++; } if (cnt[id] >= k) st[id] = true; // 如果在不大于d区间以内可以满足要求 则为true } for (int i = 0; i <= 100000; ++ i) { if(st[i]) printf("%d\n", i); // 因为这里的id的范围说出来了 所以可以一个个看 那些符合要求 } return 0; }
Java
import java.util.*; import java.io.*; public class Main { static int N = 100010; static int n, d, k; static int [] cnt = new int [N]; static PII [] logs = new PII [N]; static boolean [] st = new boolean [N]; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String [] strs = reader.readLine().split(" "); n = Integer.parseInt(strs[0]); d = Integer.parseInt(strs[1]); k = Integer.parseInt(strs[2]); for (int i = 0; i < n; ++ i) { strs = reader.readLine().split(" "); int t = Integer.parseInt(strs[0]); int id = Integer.parseInt(strs[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 <= 100000; ++ i) { if (st[i]) System.out.println(i); } } public static class PII implements Comparable<PII> { int t; int id; public PII (int t, int id) { this.t = t; this.id = id; } @Override public int compareTo(PII o) { // TODO Auto-generated method stub return Integer.compare(t, o.t); } } }
