1238. 日志统计

https://www.acwing.com/problem/content/description/1240/
首先是暴力做法,可以先循环id,再循环时间,在相同id的情况下,,枚举每个d时间段内点赞数是否大于等于k,但是这种方式不一定可以优化
可以先循环时间,再循环id,枚举整个时间范围,即枚举每个d时间段,再枚举每个行数据,查看在d时间范围内,此id是否满足要求
这题类似于滑动窗口,窗口范围不变,但是整个窗口在移动,判断窗口内的每条数据 在不断移动的窗口中(从0开始,有n种窗口),在每个窗口的条件下 是否满足要求

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

#define x first
#define y second

const int N = 100010;

int n, d, k;
PII logs[N];
bool st[N];
int cnt[N];
int maxt;
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);
        maxt=max(maxt,logs[i].x);//求最大时间
    }
    for(int i=0;i<=maxt;i++)//枚举0~maxt的所有时间段,即移动窗口
    {
        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)//从第i时间开始算,到i+d,枚举所有这个范围内的点赞数,类似于滑动窗口,窗口范围不变,但是范围的起点和终点在通过i循环移动
                cnt[id]++;
            if(cnt[id] >= k)st[id]=true;//确定热帖
        }
    }
    for(int i=0;i<N;i++)
        if(st[i])
            printf("%d\n",i);
}

纯纯暴力是无法AC的,通过分析,可以知道整个窗口只有起点和终点在变换,中间很多数据重复计算过了
这里就可以利用双指针算法了,对于整个窗口,计算的是点赞的数量,如果窗口变换向前移动一个,那么末尾的id的就不在窗口中了,因此点赞数量需要减少,而前面又新加入了一个id,出现在窗口中则此id的点赞数就需要增加,即cnt[i]--,cnt[j]++
如此就不需要枚举0~maxt的时间段了,只需要在i循环的滑动窗口中,不断地去增加新加入窗口的id和减去脱离窗口的id即可,但这里需要按照时间排序,在有序的时间内才便于计算窗口范围,以便于双指针维护窗口
双指针简介:https://www.bilibili.com/read/cv17622207/
类似的题解可以参考这篇:https://www.acwing.com/solution/content/103837/

这里的双指针是用来维护窗口区间的
如:

//若要维护一个区间,一般来说用两重循环
for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        对[i,j]的区间进行计算;
    }
这样的区间维护,每次i循环结束后,j都会重复赋值为0,大大浪费时间,时间为O(N^2)
但是用双指针的话,可以优化成这种形式:
for(int i=0,j=0;i<n;i++)
{
    while( j < i )//这里的条件是整个区间的范围,可以是类似于i-j>=xxx,区间范围为xxx
    {
        对[j,i]区间进行计算;
        j++;
    }
}
这样的优化,因为每次i或者j操作只会增加1,而且j不会重复赋值为0,实际上的时间复杂度为O(N)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 100010;
int n, d, k;
PII logs[N];
bool st[N];
int cnt[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 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]) cout << i << endl;
    return 0;
}