Author: lllyouo
Date: 20251022
tag: 队列
link: https://www.luogu.com.cn/problem/P8661

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int ts, id;

    bool operator< (const Node &x) {
        if (ts == x.ts) return id < x.id;
        else return ts < x.ts;
    }
} a[100010];
int n, d, k, vis[100010], ans[100010];
queue<int> q[100010];

int main() {
    cin >> n >> d >> k;
    for (int i = 1; i <= n; i++) {
        int ts, id; cin >> ts >> id;
        a[i] = {ts, id};
    }
    sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; i++) {
        int ts = a[i].ts, id = a[i].id;
        
        if (vis[id]) continue;

        while (q[id].size() && ts - q[id].front() >= d) q[id].pop();
        q[id].push(ts);
        if (q[id].size() >= k) {
            ans[id] = 1;
            vis[id] = 1;
        }
    }

    for (int i = 0; i < 100010; i++) {
        if (ans[i]) cout << i << endl;
    }
    
    return 0;
}