AcWing 1238. 日志统计 暴力做法
原题链接
中等
作者:
ㅤ_928
,
2024-03-05 16:28:58
,
所有人可见
,
阅读 26
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5+10;
int n,d,k;
vector<int> v[N]; // 存某一时刻对应的点赞帖子id
vector<int> ans; // 存热门帖子id序列
int st[N]; // 帖子id点赞次数
bool vis[N]; // 是否被标记过为热门帖子
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> d >> k;
for(int i = 1;i<=n;i++){
int ts,id ; cin >> ts >> id;
v[ts].push_back(id);
}
for(int i = 0;i<d;i++) // 预处理第一个长度为d的时间段
if(v[i].size()){
for(int j = 0;j<v[i].size();j++) {
st[v[i][j]] ++;
if(st[v[i][j]] >= k && !vis[v[i][j]]) ans.push_back(v[i][j]) , vis[v[i][j]] = true;
}
}
// 随后每次向后移动一个时间单元,去掉 i - d 时间的点赞,加上当前的点赞
for(int i = d ; i < N ; i++){ // 枚举整个时间段
if(v[i - d].size())
for(int j = 0;j<v[i - d].size();j++) st[v[i - d][j]] --;
if(v[i].size()){
for(int j = 0;j<v[i].size();j++) {
st[v[i][j]] ++;
if(st[v[i][j]] >= k && !vis[v[i][j]]) ans.push_back(v[i][j]) , vis[v[i][j]] = true;
}
}
}
sort(ans.begin() , ans.end());
for(int i = 0;i<ans.size();i ++) cout << ans[i] << endl;
return 0;
}