洛谷P8661 [蓝桥杯 2018 省 B] 日志统计 题解

· · 题解

暴力 排序把每个 id 相同的找出，用指针记录相同时间最后位置都成立的位置。 因为排序把 ts 按从小到大排序过了，所以不需要考虑 ts 的大小。

#include<bits/stdc++.h>
using namespace std;
struct o{
    int a,b;
}a[100005];
int n,d,k;
int cmp(o x,o y){
    if(x.b!=y.b)return x.b<y.b;
    return x.a<y.a;
}
int f1(int x,int y){
    int r=x;
    for(int i=x;i<=y;i++){
        while(a[r+1].a-a[i].a<d&&r<y)r++;//找最后一个时间和位置都成立的位置
        if(r-i+1>=k)return 1;//判断位置是i时是否是热帖
    }
    return 0;
}
int main()
{
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        int r=i;
        while(a[r+1].b==a[i].b)r++;//找到最后一个id相同的位置 
        if(f1(i,r)){//判断i到r可不可以是热帖 
            cout<<a[i].b<<endl;
        }
        i=r;
    }
    return 0;
}