看了其他大佬的题解,原谅我太菜,双指针没看懂
想法是创建二维数组,把同一个id的点赞时间放到他的子数组里,接着就是遍历,对每一个id只要k个点赞时间的两个a[x][i+k-1]和a[x][i]的时间间隔不超过d,那就可以输出,否则就pass掉
#include<iostream>
#include<vector>
#include<algorithm>
#define N 100005
using namespace std;
int n,d,k;
vector<int> a[N];
bool judg(int x)
{
int len = a[x].size();
sort(a[x].begin(),a[x].end());
for(int i = 0;i+k-1 < len;i++)
{
if(a[x][i+k-1]-a[x][i] < d)
{
return true;
}
}
return false;
}
int main(void)
{
cin>>n>>d>>k;
for(int i = 1;i <= n;i++)
{
int ts,id;
cin>>ts>>id;
a[id].push_back(ts);
}
for(int i = 0;i < N;i++)
{
if(judg(i))
{
cout<<i<<endl;
}
}
return 0;
}