题目描述

一个博主id在某天被点赞记为 t id
对每个id的点赞天号排序得到 id: t0 t0 t1 t1 t1 t3 t5 .....
查找有没有这样一个性质，即在天数跨度小于D的条件下，点赞数不少于K个。

最坏情况 O(nlgn)

只有一个id 且遍历到最后一段仍没有满足性质。

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define loop(n) for(int i=0;i<n;++i)

const int N=1e5+4;
vector<int> ids[N];
int gn,gd,gk;

bool isHot(int i){
    int det=gk-1;
    auto &me=ids[i];
    int n=me.size()-det;

    loop(n){
        //得到K个赞且不超过D天
        if(me[i+det]-me[i]<gd) return true;
    }
    return false;
}

int main(){
    cin>>gn>>gd>>gk;

    loop(gn){
        int t,id;
        scanf("%d%d",&t,&id);
        ids[id].push_back(t);
    }

    loop(N) if(!ids[i].empty()) sort(ids[i].begin(),ids[i].end());

    loop(N) if(!ids[i].empty()&&isHot(i)) cout<<i<<endl;

    return 0;
}