6、日志统计

题目 日志统计

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n, d, k;

unordered_map<int, vector<int>> likes; //帖子id 该id的所有点赞情况

set<int> hotPosts; // 存答案id

int main() {

    cin >> n >> d >> k;

    while(n--) {

        int ts, id;

        cin >> ts >> id;

        likes[id].push_back(ts);

    }

    for(auto &p : likes) {

        vector<int> &timestamps = p.second;

        sort(timestamps.begin(), timestamps.end());

        // 滑动窗口 （没必要前缀和 反而麻烦）

        for(int i = 0; i < timestamps.size(); i++) {

            int count = 0;

            for(int j = i; j < timestamps.size() && timestamps[j] < timestamps[i] + d; j++) {

                count++;

                if(count >= k) {

                    hotPosts.insert(p.first);

                    break;

                }

            }

        }

    }

    for(int id : hotPosts) {

        cout << id << endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 5、递增三元组 🏠 00-刷题理模型 ➡️ 8、乘积最大