题目描述

题目省略，解析见代码注释,本人算法小白，这个题一遍过，很自然出来的思路

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef struct PA{
    int ts;
    int id;
} pa;

//按id升序排序，若id相等则按ts升序排序
bool compare(pa t1, pa t2){
    if(t1.id==t2.id)
        return t1.ts<t2.ts;
    return t1.id<t2.id;
}

int main(){
    int N,D,K;
    cin>>N>>D>>K;
    vector<pa> r(N,pa());
    for(int i = 0; i < N; i++){
        cin>>r[i].ts>>r[i].id;
    }
    sort(r.begin(),r.end(),compare);
    int left = 0;
    int right = 0;
    vector<int> ans;
    //双指针，形成滑动窗口，左闭右开
    while(right<N){
        if(right==left){
            right++;
        }
        else{
            //id不相同，直接窗口清零
            if(r[right].id!=r[left].id){
                left = right;
                continue;
            }
            else{
                //id相同，且时间差小于D，则right++,窗口大小加一
                if(r[right].ts-r[left].ts<D){
                    right++;
                }
                else{
                    //时间差大于D，将左边的指针向前移，相当于窗口大小减一
                    left++;
                }
            }
        }
        //窗口大小等于K，即找到一个答案，记录id
        if(right-left==K){
            ans.push_back(r[right-1].id);
            int temp = r[right-1].id;
            while(right<N){
                if(r[right].id!=temp)//跳过已记录的id
                    break;
                right++;
            }
            left = right;
        }
    }
    //处理最后可能遗漏的数据
    if(right-left==K){
        ans.push_back(r[right-1].id);
        left = right;
    }
    for(int i = 0; i < ans.size(); i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}