C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

双指针

$for循环枚举所有时间，[j, i) 表示 [T,T+D)，有符合条件的，标记一下$

$时间复杂度：O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

const int N = 1e5 + 10;
typedef pair<int, int> pii;

int n, d, k;
pii log[N];
int cnt[N];
bool st[N]; // 记录某个帖子是否是热帖

int main() {
    cin >> n >> d >> k;
    for (int i = 0; i < n; i ++) cin >> log[i].x >> log[i].y;

    sort(log, log + n);


    for (int i = 0, j = 0; i < n; i ++) { // 枚举时间段，i:右端点 j:左端点
        int id = log[i].y;
        cnt[id] ++;

        while (log[i].x - log[j].x >= d) { 
            cnt[log[j].y] --;
            j ++;
        }
        if (cnt[id] >= k) st[id] = true; // 符合
    }

    for (int i = 0; i <= 1e5; i ++)
        if (st[i])
            cout << i << endl;

    return 0;
}