AcWing 1238. 日志统计 枚举时间降低复杂度
原题链接
中等
作者:
ysl0310
,
2021-03-10 08:51:32
,
所有人可见
,
阅读 331
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a[100010];
int n,d,k;
vector<int> ans;
int main()
{
cin>>n>>d>>k;
for(int i=0;i<n;i++){
int n1,n2;
scanf("%d%d",&n1,&n2);
a[n2].push_back(n1);
}
for(int i=0;i<100001;i++){
sort(a[i].begin(),a[i].end());
int p1=0,p2=0,flag=0,cnt=0;
for(int p2=0;p2<a[i].size();p2++)
{
cnt++;
while(a[i][p2]-a[i][p1]>d-1) {p1++;cnt--;}
if(cnt>=k&&!flag){flag=1;ans.push_back(i);} ;
}
}
for(int x:ans) printf("%d\n",x);
return 0;
}