AcWing 1238. 日志统计(双指针 + 队列)
原题链接
中等
作者:
Virmar
,
2024-03-05 14:40:43
,
所有人可见
,
阅读 12
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1E5 + 6;
int n, d, k; // 如题
struct node{ // 存题目给出的点赞时间和id
int t, id;
bool operator<(node x) { // 按照 id 为第一关键字 t 为第二关键字排序
if (id == x.id) return t < x.t;
return id < x.id;
}
} a[N];
int q[N];
int hh, tt;
bool solve(node b[], int m) {
// 特判,至于为什么要加这一句,是因为我先放入一个元素然后在循环中进行判断,如果不加在 m = 1 时会直接返回 false
if (k == 1) return true;
hh = 1, tt = 0;
q[++tt] = b[1].t; // 将第一个元素放入队列
for (int i = 2; i <= m; i++) {
int now = b[i].t; // 当前点赞的时间
while (hh <= tt and q[hh] <= now - d) hh++; // 与当前时间相差超过 d 的元素都出队
q[++tt] = now; // 然后加入现在的点赞时间
if (tt - hh + 1 >= k) return true; // 长度超过 k 表示点餐数量超过 k 返回 true
}
return false;
}
int main() {
cin >> n >> d >> k;
for (int i = 1; i <= n; i++)
cin >> a[i].t >> a[i].id;
sort(a + 1, a + n + 1);
/**
* 双指针,a[i] ~ a[j - 1] 为 id 相同的部分
* solve 函数表示对 id 相同的部分进行判断,第一个参数为相同部分的第一个元素,第二个为相同部分的长度
* 应该传入 a + i,但是为了 solve 函数种处理能够以 1 开始,所以传入 a + i - 1,长度就是 (j - 1) - i + 1 == j - i
*/
int i = 1;
while (i <= n) {
int j = i + 1;
while (j <= n and a[j].id == a[j - 1].id) j++;
if (solve(a + i - 1, j - i)) cout << a[i].id << endl;
i = j;
}
return 0;
}