#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=100010;
int n,d,k;//日志个数,区间长度,热度标准
PII logs[N];//记录 时间点与帖子的id
int cnt[N];//记录每个帖子的点赞数
bool st[N];//记录每个帖子是否曾经是热帖
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>d>>k;
for(int i=0;i<n;i++)
{
cin>>logs[i].x>>logs[i].y;
}
//将所有的记录按照时间进行排序
sort(logs,logs+n);//时间相同时,对id大小进行排序,默认都是由小到大
//双指针
//i在for后面的括号里循环,j在for语句体中循环
for(int i=0,j=0;i<n;i++)//i与j哪个在前哪个在后都可以 在前面的是右端点,在后面的是左端点
{
int id=logs[i].y;//注意i代表第几条记录,而不是第几时刻
cnt[id]++; //对应时刻的点赞量加一
//当第i条记录的时间与第j条记录的时间跨度大于等于d(因为左闭右开区间)的时候,需要进行到下一个时间区间
//也就是i与 j都加1
//下一个时间区间与当前时间区间的区别只在开头与结尾
//当前时间区间的开始时刻(是j时刻)的点赞需要取消,所以进行--操作
//下一个时间区间的结束时刻的点赞会在i循环的时候自动增加
//当j==i时会停止 ,所以不会死循环
while(logs[i].x-logs[j].x>=d)
{
cnt[logs[j].y]--;
j++;
}
if(cnt[id]>=k) st[id]=true; //达到热帖标准,记录下来
}
for(int i=0;i<=100000;i++)
{
if(st[i])
cout<<i<<endl;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla