日志统计(C++,模拟，双指针)

 题目要我们求在某个时间段中，帖子点赞数达到K的帖子数

遍历方式一

我们可以先对所有帖子根据时间，升序排序

枚举每一条帖子，枚举后续每一条帖子，如果id相同且时间差小于d，那么就记录起来，如果记录数量cnt大于K那么就是热帖

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10;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);for (int i = 0;i < n;i++) {int id1 = logs[i].y,ts1 = logs[i].x,cnt = 0;for (int j = i;j < n;j++) {int id2 = logs[j].y,ts2 = logs[j].x;if (ts2 - ts1 >= d) break;if (id2 == id1 ) cnt++;}if (cnt >= k) st[id1] = true;}for (int i = 0;i < N;i++) {if (st[i]) {printf("%d\n",i);}}return 0;
}

遍历方式二

另外一种遍历方式，我们可以先遍历时间段，再遍历帖子

先枚举所有的帖子，如果该帖子在时间段内，那么cnt++

如果该时间段内点赞数＞K，那么将它设置为热帖

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5 + 10;int n,d,k;
PII logs[N];
int cnt[N];
bool st[N];int main() {scanf("%d%d%d",&n,&d,&k);int maxt = 0;for (int i = 0;i < n;i++) {scanf("%d%d",&logs[i].x,&logs[i].y);maxt = max(logs[i].x,maxt);}sort(logs,logs+n);for (int i = 0;i <= maxt;i++) {memset(cnt,0,sizeof cnt);for (int j = 0;j < n;j++) {int id = logs[j].y;int t = logs[j].x;if (t >= i && t < i + d) cnt[id]++;if (cnt[id] >= k ) st[id] = true;}}for (int i = 0;i < N;i++) {if (st[i]) printf("%d\n",i);}return 0;
}

利用双指针思想优化 

由于我们时间段大小是固定的，因此每次时间段的改变只需要减掉开头，尾部加入，所有会有很多的多余操作，所以我们可以用双指针来维护一个区间

遍历所有的帖子，t表示该帖子的时间，也是时间段段的开头

while循环维护时间段，如果t-logs[j].x >= d 即 时间相近的两个帖子的时间差超过d了，那么j这个帖子的点赞数就要减少

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5 + 10;int n,d,k;
PII logs[N];
int cnt[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);for (int i = 0,j = 0;i < n;i++){int t = logs[i].x,id = logs[i].y;cnt[id]++;while (t - 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;
}