题目描述

日志统计

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100001;
vector<int> s[N];
int n, d, k;
map<int,bool> vis;
vector<int> mid;
bool check(int id){
    // 1 3 7 10 12  k=3 d=5
    //0 10
    int size = s[id].size();
    if (size < k) return false;
    sort(s[id].begin(), s[id].end());
    int l = 0, r = 0;
    int sum = 1;
    while (l <= r){
        sum++, r++;
        if (r>=size)break;
        if (sum >= k){
            if (s[id][r] - s[id][l] < d)return true;
            l++, sum--;
        }
    }
    return false;
}

int main(){
    cin >> n >> d >> k;
    for (int i = 1; i <= n; i++){
        int id, ts; 
        cin >> ts >> id;
        if (!vis[id]){
            vis[id] = 1;
            mid.push_back(id);
        }
        s[id].push_back(ts);
    }
    sort(mid.begin(), mid.end());
    for (int i = 0; i < mid.size(); i++){
        if (check(mid[i]))cout << mid[i] << '\n';
    }
    return 0;
}