球球各位给蒟蒻一个免费的赞

这里附上暴力做法和滑动窗口优化的方法

这题的主要细节是滑动窗口，但这题的最巧妙的地方在于排序

如果是传统的直接用滑动窗口难免无从下手，难点在每个店铺的热度的判定都对应一个起始时间和结束时间，难道开多个滑动窗口吗？排序为我们很好的解决了这一点，下面具体看代码分析

先看优化，暴力可以看下面

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;//y总pair小技巧
const int N=1e5+10;
int cnt[N];//cnt用来记录滑动窗口内订单的次数
bool st[N];//st用来记录是否曾为热度订单
PII a[N];//a代表的是订单
int b[N];
int hh=0,tt=-1;
int n,d,k1;

bool cmp(PII a,PII b){
    return a.x<b.x;
}//写一个排序函数，让订单按时间排序

signed main(){
    cin>>n>>d>>k1;
    for(int i=1;i<=n;i++){
        int ts,id;
        cin>>ts>>id;
        a[i]={ts,id};
    }//读入订单

    sort(a+1,a+1+n,cmp);//将订单按排序

    for(int i=1,j=1;i<=n;i++){
        int id=a[i].y;
        cnt[id]++;//店铺热度加一
        while(a[i].x>=a[j].x+d){//时间长度超过窗口长度，进行出队列
            cnt[a[j].y]--;
            j++;
        }//这里就是最经典的核心代码了
        //如果我们采取正常的单调队列，我们需要开许多单调队列模拟滑动窗口
        //但注意到订单按时间排序
        //如果时间靠前的订单关于对应的店铺来说要出队列了
        //那么该订单对于后面的订单对应的店铺来说也一定要出队列
        //所以j一定只会向后移动而不会向前移动
        //这样就可以只用一个j就实现窗口长度的维护了
        if(cnt[id]>=k1)st[id]=true;//如果窗口内店铺热度达到标准就打上标记
    }

    for(int i=1;i<=1e5;i++)if(st[i]==true)cout<<i<<endl;
    //因为不知道最大店铺，所以要遍历所有店铺，来看哪些店铺曾是热度店铺

    return 0;
}

暴力啦,我是最简单实现的暴力了，过了7个样例

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int  c[N];
bool st[N];
int h[N],e[N],ne[N],idx,cnt;
int n,d,k1;

signed main(){
    cin>>n>>d>>k1;
    //cout<<n<<d<<k<<endl;
    int tm=0;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        int t,id;
        cin>>t>>id;
        e[idx]=id;
        ne[idx]=h[t];
        h[t]=idx++;
        tm=max(tm,t);
    }
    //cout<<tm<<endl;

    for(int i=0;i<=tm+1;i++){
        memset(a,0,sizeof a);
        //if(i==100)cout<<'#'<<endl;
        for(int j=i;j<i+d&&j<=tm;j++){
           // if(j==100)cout<<'%'<<endl;
            for(int k=h[j];k!=-1;k=ne[k]){
                int m=e[k];
                a[m]++;
               // cout<<j<<' '<<m<<' '<<a[m]<<endl;
                if(a[m]>=k1&&!st[m]) {c[cnt++]=m,st[m]=true;}
            }
        }
        //cout<<endl<<endl<<endl;
    }

    //cout<<cnt<<endl;
    sort(c,c+cnt);
    for(int i=0;i<cnt;i++) cout<<c[i]<<endl;

    return 0;
}