AcWing 1238. 日志统计
原题链接
中等
作者:
zjdhr1
,
2021-04-05 16:24:52
,
所有人可见
,
阅读 264
用结构体存每一个帖子被点赞的时间,因为数据给的是乱序的,所以在查找前给每一个帖子所代表的vector升序排序,并开始查找,如果点赞数大于等于K就break并输出该帖子的id
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node{
vector<int> v;
};
node arr[N];
int main()
{
int n , t , k;
scanf("%d %d %d" ,&n , &t , &k);
int minn = INT_MAX , maxx = INT_MIN;
for (int i = 1 ; i <= n ; i++)
{
int a , b;
scanf("%d %d" , &a , &b);
arr[b].v.push_back(a);
minn = min(minn , b);
maxx = max(maxx , b);
}
for (int i = minn ; i <= maxx ; i++)
{
if (arr[i].v.size())
{
sort(arr[i].v.begin() , arr[i].v.end());
int tag = 0;
for (int j = 0 ; j < arr[i].v.size() ; j++)
{
int ret = arr[i].v[j];
int num = 1;
for (int p = j + 1 ; arr[i].v[p] < ret + t && p < arr[i].v.size() ; p++) num++;
if (num >= k)
{
tag = 1;break;
}
}
if (tag) cout << i << endl;
}
}
return 0;
}