AcWing_1238 日志统计(滑动窗口)

01 Apr 2024 762字 3分

AcWing

1238. 日志统计

首先对所有日志按时间递增排序，之后时间段d的窗口在排序后的序列中取。

初始化左、右端点i=1, j=1；

  • 移动右端点i，每次移动使得cnt[log[i].id] ++；
    • 对于每个右端点i，向右移动左端点j，直到左右端点所表示的时间范围在时间段d之内，每一次移动左端点j，将移出的左端点j所代表的id的获赞次数-1；
    • 此后，如果cnt[log[i].id] >= k，那么认为这个帖子曾是热帖。
#include <bits/stdc++.h>
using namespace std;
int n, d, k;
const int N = 100010;
typedef pair<int, int> PII;
#define ts first
#define id second
PII logs[N];
int cnt[N];
bool ishot[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> d >> k;
    for(int i = 1; i <= n; i ++) cin >> logs[i].ts >> logs[i].id;
    sort(logs + 1, logs + 1 + n);
    for(int i = 1, j = 1; i <= n; i ++){
        int t = logs[i].id;
        cnt[t] ++;
        while(logs[i].ts - logs[j].ts >= d){
            cnt[logs[j].id] --;
            j ++;
        }
        if(cnt[t] >= k) ishot[t] = true;
    }
    for(int i = 0; i <= 100000; i++) if(ishot[i]) cout << i << '\n';
    return 0;
}