当前位置：首页 > news >正文

蓝桥杯 11.日志统计

news 2025/7/5 12:45:18

日志统计

题目描述

小明维护着一个程序员论坛。现在他收集了一份 “点赞” 日志，日志共有 N 行。其中每一行的格式是：

ts id

表示在 ts 时刻编号 id 的帖子收到一个 “赞”。

现在小明想统计有哪些帖子曾经是 “热帖”。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是 “热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T, T+D) 这段时间内（注意是左闭右开区间）收到不少于 K 个赞，该帖就曾是 “热帖”。

给定日志，请你帮助小明统计出所有曾是 “热帖” 的帖子编号。

输入描述

输入格式：

第一行包含三个整数 N D K。

接下来的 N 行，每行包含两个整数 ts 和 id。

1 ≤ K ≤ N ≤ 10^5
0 ≤ ts ≤ 10^5
0 ≤ id ≤ 10^5

输出描述

按从小到大的顺序输出热帖 id，每个 id 一行。

输入输出样例

输入

输出

1
3

c++代码

#include<bits/stdc++.h>using namespace std;unordered_map<int, queue<int>> mp;
vector<vector<int>> arr;
unordered_set<int> ans;
vector<int> tem;int N, D, K, ts, id, k;bool mycom(vector<int>& a, vector<int>& b) { return a[0] < b[0]; }int main() {cin >> N >> D >> K;arr = vector<vector<int>>(N, vector<int>(2));for (int i = 0; i < N; i++) cin >> arr[i][0] >> arr[i][1];sort(arr.begin(), arr.end(), mycom);for (int i = 0; i < N; i++) {if (ans.find(arr[i][1]) != ans.end()) continue;mp[arr[i][1]].push(arr[i][0]);if (mp[arr[i][1]].size() == K) {k = mp[arr[i][1]].front(), mp[arr[i][1]].pop();if (arr[i][0] - k < D) ans.insert(arr[i][1]);}}for (int x : ans) tem.push_back(x);sort(tem.begin(), tem.end());for (int x : tem) cout << x << endl;return 0;
}//by wqs