原题链接
双指针 + 枚举时间 + 离散化去重
本来看题面觉得这题复杂,结果一遍敲完没有调试直接就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;
}
不错不错,我喜欢看 https://www.237fa.com/
叼茂SEO.bfbikes.com