题目描述

双指针没有固定模版，只是一种优化思想，当有i和j两个变量在循环时就是双指针
本题有两种思路：1.循环id（不好弄）
2.循环长度为d的时间段，这样可以用双指针优化

样例

#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int ,int>PII;//这是一种类型的数组

const int N=100010;
int n,d,k;
int cnt[N];
PII logs[N];
bool st[N];

int main(){
    scanf("%d%d%d",&n,&d,&k);
    for(int i=0;i<n;i++)
    scanf("%d%d",&logs[i].x,&logs[i].y);

    sort(logs,logs+n);//对于PII类型数组，sort会按照first即第一个数去排序，如果第一个相同，会按照第二个排序

    for(int i=0,j=0;i<n;i++){//i在前面走，j在后面追
        int id=logs[i].y;
        cnt[id]++;//记录下编号为id的帖子出现的次数

        while(logs[i].x-logs[j].x>=d){//找到长度为d的时间段
        cnt[logs[j].y]--;//删去头!!!i是走在前面的，头应该是j！！！！你一开始写的是i，还觉得自己“明明和y总写的一模一样，为啥不对？”
            j++;//这两行可以保持d的长度往后移
        }
        if(cnt[id]>=k) st[id]=true;//如果id出现的次数>=k,那她就是热帖

    }
    for(int i=0;i<=100010;i++){
        if(st[i])
        printf("%d\n",i);
    }

    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla