摘要
Title: 1238. 日志统计
Tag: 二分、双指针
Memory Limit: 64 MB
Time Limit: 1000 ms

1238. 日志统计

题意

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。
其中每一行的格式是：
ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
思路

题目问: 有多少个帖子，在任意[T, T + D - 1]的时间段中，赞的数目大于等于K

一开始想到二分来做，先按照帖子的大小和帖子的时刻排序，每个帖子维护一个数组，维护的是赞的时刻 $T$ ，每次二分 $T+D-1$ 的点，如果两者下标之间满足要求，那么这个贴就是热榜，用个哈希表标记即可
代码十分简略，而且很好想

相似题：Link

双指针，先用时刻排序，每次当时刻超出了，就让j++，并减去开头，加上结尾即可

代码

二分

'''
Author: NEFU AB-IN
Date: 2022-03-28 19:45:51
FilePath: \ACM\Acwing\1238.py
LastEditTime: 2022-03-28 20:02:39
'''
from bisect import bisect_left
from collections import Counter, defaultdict

d = defaultdict(list)
res = Counter()

n, D, k = map(int, input().split())
order = []

for i in range(n):
    ts, id = map(int, input().split())
    order.append([id, ts])

order.sort()

for id, ts in order:
    if res[id]:
        continue
    d[id].append(ts)
    res[id] = (len(d[id]) - bisect_left(d[id], ts - D + 1) >= k)

for key in res.keys():
    if res[key]: print(key)

双指针

'''
Author: NEFU AB-IN
Date: 2022-03-28 19:45:51
FilePath: \ACM\Acwing\1238.py
LastEditTime: 2022-03-28 20:02:39
'''
from collections import Counter

cnt = Counter()
res = Counter()

n, D, k = map(int, input().split())
order = []

for i in range(n):
    ts, id = map(int, input().split())
    order.append([ts, id])

order.sort()

j = 0
for ts, id in order:
    if res[id]:
        continue
    cnt[id] += 1
    while ts - order[j][0] >= D:
        cnt[order[j][1]] -= 1
        j += 1
    if cnt[id] >= k: res[id] = 1

for key in sorted(res.keys()):
    if res[key]: print(key)

1238. 日志统计

题意

思路

代码