原题链接

双指针 + 枚举时间 + 离散化去重

本来看题面觉得这题复杂，结果一遍敲完没有调试直接就ac了（运气爆棚）。

我来说说我的思路吧，其实这道题双指针循环的顺序特别像这道题 799. 最长连续不重复子序列

我们首先开一个二维数组point存一下每个时刻会出现哪些点，以便后面枚举时间的时候可以统计。

只需要在每次遍历j指针的时候统计一下每个帖子点赞的次数，在i指针划出窗口的时候将帖子点赞的次数减一，就可以动态的维护i~j窗口内每个帖子点赞的次数，在维护过程中如果发现某帖子点赞次数大于等于k就直接将该帖子放入答案数组ans

需要注意的是，ans数组可能是无序的并且存在重复元素，那我们该怎么得到答案呢？其实这一步就是离散化的三个操作，sort,erase和unique。

sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());

这样ans数组存的就是我们的答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
vector<int> point[N]; //每个时刻的点
int n,d,k;
int cnt[N]; //记录每个帖子出现的次数
vector<int> ans;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>d>>k;
    for(int i=0;i<n;i++)
    {
        int t,id;
        cin>>t>>id;
        point[t].push_back(id);
    }
    
    for(int i=0,j=0;i<N;i++)
    {
        while(j-i+1<=d&&j<N)
        {
            if(point[j].size())
            {
                for(auto id:point[j])
                {
                    cnt[id]++;
                    if(cnt[id]>=k) ans.push_back(id);
                }
            }
            j++;
        }
        
        if(point[i].size())
        {
            for(auto id:point[i]) cnt[id]--;
        }
    }
    
    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    for(auto i:ans) cout<<i<<endl;
    
    return 0;
}