算法1
(暴力枚举) $O(n^2)$
最暴力的思想,会TLE
1.pair存每个帖子的数据(时间和id)
2.按照时间排序
3.开始遍历时间,每一段长度是d i~i+d-1;
4.注意最大时间也要遍历到,遍历的时候i+d-1,要给t += 1;
5.开始计数,每个时间段对每个id计数,计数完之后判断是否满足要求,满足的话打上标记,放入答案序列。
6.对答案排序。
时间复杂度
O(d*maxt) (时间段大小 * 最大时间点)
大概$O(n^2)$
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n,d,k;
pair<int,int> in[N];
int ans[N],cnt;
int a[N];
bool st[N];
int main()
{
cin>>n>>d>>k;
int t = -1;
for(int i = 0;i < n;i++)
{
cin>>in[i].first>>in[i].second;
t = max(t,in[i].first);
}
t += 1;
sort(in,in + n);
for(int i = 0;i + d <= t;i++)
{
memset(a,0,sizeof a);
int s = i,ed = i + d -1;
for(int j = 0;j < n;j++)
{
int id = in[j].second;
if(in[j].first > ed)break;
if(in[j].first >= s) a[id]++;
if(a[id] >= k && !st[id]) ans[cnt++] = id,st[id]= true;
}
}
sort(ans,ans+cnt);
for(int i= 0;i < cnt;i++)cout<<ans[i]<<endl;
return 0;
}
感觉暴力更难写。