蓝桥杯2018年第九届真题-日志统计(复杂度O(nlogn))

解题思路:
首先记录每个日志的点赞时间，对每个日志的时间排序后，直接判断当前点赞时间和后k个时间是否差值小于d。
注意事项:
复杂度O(nlogn)

参考代码:

#include<bits/stdc++.h>
using namespace std;
#define maxx 110000
int k,a,b,n,m,d;
vector<int> all[maxx];
vector<int> ans;
int main()
{
  cin>>n>>d>>k;
  for(int i=1;i<=n;++i)
  {cin>>b>>a;
   m=max(a,m);
   all[a].push_back(b);
  }
  for(int i=0;i<=m;++i)  sort(all[i].begin(),all[i].end());
  for(int i=0;i<=m;++i)  
  for(int j=0;j+k-1<all[i].size();++j)
   if(all[i][j+k-1]-all[i][j]<d)
    {ans.push_back(i);
    break;}
  for(int i=0;i<ans.size();++i) cout<<ans[i]<<"\n";  
}