题目描述
blablabla
样例
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sstream>
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> pll;
pll logs[N];
bool flag[N]; //标记是否是热帖
int cnt[N]; //记录id编号的贴子数
int n,d,k;
int main(int argc, char** argv) {
cin>>n>>d>>k;
for(int i=0;i<n;i++){
cin>>logs[i].x>>logs[i].y;
}
//输出格式要求id从小到大;先按照x从小到大排列,若x相同,则y按从小到大排列
sort(logs,logs+n);
//双指针i,j(快慢指针)确定一个区间//i在前,j 在后
for(int i=0,j=0;i<n;i++){
int id = logs[i].y;//取出i时刻的id号;
cnt[id]++;//在i时刻的对应id号加一;
while(logs[i].x-logs[j].x>=d){
//将对应id号过期的帖子删掉
cnt[logs[j].y]--;
j++;
}
//如果id号的帖子数大于k则标志为热帖
if(cnt[id]>=k){
flag[id] = true;
}
}
for(int i=0;i<=100000;i++) {
if(flag[i]){
cout<<i<<endl;
}
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla