题目描述

以下 N 行每行一条日志，包含两个整数 ts 和 id，表示ts时刻id的帖子受到一条赞
计算D时间段内点赞数超过K（热帖）的帖子，一次输出

(双指针（左右指针）) $O(n)$

将n条数据，更据时刻排序，先选取长度为D的时段，计算有无热帖，之后移动左右指针，只需要计算收尾指针变化带来的数目变化即可，最后输出

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct Post {
    int time;
    int id;
}Post;
Post a[100010];  //存放输入的数据组
bool st[100010]; //记录id是否为热帖，若st[i]=true，表示id为热帖
int sum[100010]; //sum[i]记录当前时段,id为i的帖子点赞数目和
bool cmp(Post x, Post y) {
    if (x.time < y.time) {
        return true;   //严格小于时返回true，否则报错
    }
    return false;
}
int main()
{
    int n, d, k;

    cin >> n >> d >> k;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].time, &a[i].id);
    }
    sort(a + 1, a + n + 1, cmp);  //排序，时刻小的在前面
    /*for (int i = 1; i <= n; i++) {
        cout<<a[i].time<<"  "<<a[i].id<<endl;
    }*/
    for (int i = 1, j = 1; i <= n; i++) {
        int ID = a[i].id;
        sum[ID]++;
        while (a[i].time - a[j].time >= d) { //若a[i]对应时刻比a[j]对应时刻差值大与d

            sum[a[j].id]--;  //对应数字--
            j++;   //左指针右移
        }
        if (sum[ID] >= k) st[ID] = true; //若大于k，说明是热帖，记录
    }
    for (int i = 1; i <= 100005; i++) {  //输出
        if (st[i]) {
            cout << i << endl;
        }
    }

    return 0;
}