对于日志统计这一道题,我一开始有三个问题:
while(logs[i].x - logs[j].x >= d)
{
cnt[logs[j].y] --;
j ++;
}
这段代码为什么不用考虑日志的对象是否相同这个问题?
if(cnt[id] >= k) st[id] = true;
还有每次循环的末尾为什么只用判断滑动窗口的尾部的日志的id是否符合条件
while(logs[i].x - logs[j].x >= d)
以及这段代码为什么是i-j
经过我研究学习了几个大佬写的题解后好像有点理解了
首先第一个问题,因为我们在进行滑动窗口处理前,就进行了排序操作,把所有的日志按照日期进行了降序排列,而滑动窗口的本质就是维护一个长度为d的框框,让它在整个数组中进行滑动,更加直白的说法是,我们是在枚举一个个长度为d的时间段,统计这个时间段内所有的点赞数,并将点赞数满足条件的id设为热门。所以,这段代码的思路是枚举一个个时间段,再去判断在这个时间段中出现的id是否符合条件。因此,并不需要对象相同。
ok,接下来一定会有小朋友问了,为什么枚举完每一个时间段后,不需要判断所有的在这个时间段出现过的id是否符合条件呢?
这里就体现出滑动窗口思想的精妙性了,众所周知,我们枚举的两个相邻的时间段,只有开头和末尾的数据不一样,就像这个小框框滑动了一格一样。在这道题里面就是相当于开头的日志被作废了,与此同时,末尾新加入了一个日志。
举个极端的例子来让大家理解吧:
假设在第i个时间段,滑动窗口开头的日志的帖子为x,也就是说,在第i个时间段的开头它就已经得到了一个赞,在这个时间段内,它又获得了k - 1个赞,满足了热门帖子的条件,而当我们的窗口滑动到下一个时间段后,它的第一个赞已经作废了,如果末尾加入的不是它的日志,那么它就已经不满足热门帖子的条件了。所以说,第i个时间段是帖子x满足条件的最后时间,如果这个时间段不进行判断的话,我们就会漏解,因此,我们每次进行滑动时,都只判断那个接近极限的id是否满足条件即可。
最后为什么i是时间段末尾j是时间段开头这个问题,因为y总是这么写的,其实也有反过来的写法,大家可以参考参考其他大佬写的题解。
如果还是不理解滑动窗口的算法的话也可以去看一看网上的模拟动画~
最后附上源代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
PII logs[N];
int cnt[N];
int n, d, k;
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);
for(int i = 0, j = 0; i < n; i ++) //i为滑动窗口末端
{
int id = logs[i].y;
cnt[id] ++;
while(logs[i].x - logs[j].x >= d)
{
cnt[logs[j].y] --;
j ++;
}
if(cnt[id] >= k) st[id] = true;
}
for(int i = 0; i < N; i ++)
{
if(st[i]) printf("%d\n", i);
}
return 0;
}