“热帖”统计

原题链接：日志统计

struct log
{
    int t, id;
    bool operator<(const log &L) const
    {
        return t < L.t;
    }
} logs[N];
1
2
3
4
5
6
7
8

朴素做法

枚举所有长度为$D$的时间段，统计在该时间段内，每个帖子收到的赞数，从而得出“热帖”。

sort(logs, logs + n); //将所有点赞记录按照时间进行排序

for (int t = 0; t <= 100001 - D; t ++) //枚举每个时间段
{
    memset(cnt, 0, sizeof(cnt));
    
    for (int i = 0; i < n; i ++) //遍历每个记录
        if (t <= logs[i].t && logs[i].t < t + D) //该点赞记录在该时间段内
        {
            int id = logs[i].id;
            cnt[id] ++;
            if (cnt[id] >= K) st[id] = true;
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

TLE

双指针做法

注意到：第$i$个时间段与第$i+1$个时间段中有许多记录是相同的。

因此采用双指针来遍历所有记录，维护指针$j,i$使其为长为$D$的时间段的两端。

注意：由于按序枚举，$i$指针的每次移动都会使某个帖子的点赞数增加，因此 $i$指针的移动是产生“热帖”的直接导引，即最新产生的“热帖”一定是$i$所指向的帖子，因此每次只需判断$i$指针所指的帖子是否为热帖即可。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
struct log
{
    int t, id;
    bool operator< (const log &L) const
    {
        return t < L.t;
    }
} logs[N];
int cnt[N];
bool st[N];  // st[id]记录着帖子id是否是热帖

int main()
{
    int n, D, K;
    cin >> n >> D >> K;
    for (int i = 0; i < n; i ++) cin >> logs[i].t >> logs[i].id;

    sort(logs, logs + n); //将点赞记录按照时间进行排序

    for (int i = 0, j = 0; i < n; i ++) //双指针枚举每个记录，j、i指向的是时间段的两端
    {
        int id = logs[i].id; //i指向一个新的记录
        cnt[id] ++;

        while (logs[j].t + D <= logs[i].t) cnt[logs[j].id] --, j ++; //调整j，使j~i在同一个时间段中
        if (cnt[id] >= K) st[id] = true; //在该时间段中，id是热帖
    }

    for (int id = 0; id <= 100000; id ++)
        if (st[id]) cout << id << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39