蓝桥杯 11.日志统计

日志统计

题目描述

小明维护着一个程序员论坛。现在他收集了一份 “点赞” 日志，日志共有 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 一行。

输入输出样例

输入

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;

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

思路解析

按时间顺序维护一个点赞队列，当点赞队列的元素个数等于K的时候，判断是否满足时间要求，判断的话弹出第一个元素和当前元素比较就行。