题目描述

很原始的做法 支持dvc++11版本一下 而且思路很简单

样例

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int>t[N]; 
int cnt[N];//表示在d区间时刻里 id被点赞的数目
set<int>s; 
int main(){
    int n,d,k;cin >> n >> d >> k;
    while(n --){
        int ts,id;cin >> ts >> id;
        t[ts].push_back(id);
    }
    for(int i = 0;i < d;i ++){
        for(int j = 0;j < t[i].size();j ++){
            cnt[t[i][j]] ++;
            if(cnt[t[i][j]] >= k)s.insert(t[i][j]);
        }
    }
    //注意注意注意从0开始的下标
    for(int i = d;i < N ;i ++){
        for(int j = 0;j < t[i - d].size();j ++){
            cnt[t[i - d][j]] --;
        }
        for(int l = 0;l < t[i].size();l ++){
            cnt[t[i][l]] ++;
            if(cnt[t[i][l]] >= k)s.insert(t[i][l]);
        }
    }
    set<int>::iterator it;
    for(it = s.begin();it != s.end();it ++){
        cout << *it <<"\n";
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla