【蓝桥杯练习--双指针】1238.日志统计

题目：1238. 日志统计

• 日志就是记录
• 暴力解法：

1. 先for循环多个时间段
2. 循环每个时间段内每个帖子被点赞的数量
3. 如果帖子的数量大于等于K，则说明是热帖

伪代码如下：

for(时间段)							//循环多个时间段
{
    //memset清空
    memset(cnt,0,sizeof cnt);   	//循环每个时间段内
    for(id)							//循环此时间段内的所有id
    {
        cnt[id]++;					//cnt记录被点赞次数
        if(cnt[id]>=k) st[id]=true;	//如果点赞次数超过k 就是热帖
    }
}
for(int i=1;i<=100000;i++)			//输出热帖
    if(st[i])
        cout << i << endl;

           

• 但暴力解法的时间复杂度为 (N * N) 或 (N * D) ，会超时，所以考虑优化（将二重循环for减为一重循环）
• 因为每次遍历的时间段在本质上只是整体向后移动了一位，中间内容相同、不改变，只有首尾发生变化，所以只需要将原来第一位减去再向后加一位即可，此时的时间复杂度为O(N)
• 本质上i，j同时增加（即双指针：两个坐标一前一后一起改变），只遍历了一遍

伪代码：

for(时间段)
{
    cnt[id[i]]--;   //减去开头
    cnt[id[j]]++;   //加上结尾
}
for(int i=1;i<=100000;i++)
    if(st[i])
        cout << i << endl;
           

代码：

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

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;  //pair排序（默认以first为第一关键字，second为第二关键字排序）

const int N=100010;

int n,d,k;      //数量 时间段长度 热帖标准
PII logs[N];    //记录（logs是一个结构体数组）
int cnt[N];     //所有ID出现的次数
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);  //将所有的记录按时间排序（与sort排序函数的区别？可以替换为sort吗）
    
    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<=100000;i++)
        if(st[i])
            printf("%d\n",i);
    return 0;
}
           

相关链接：

1. memset

2. pair

   将两个属性值放在一起构成一个新的结构体类型（类似stl中的map 是将value和key结合起来）

   因为是结构体，所以可以直接访问其中的变量

   排序时会首先根据第一关键字进行排序，然后根据第二关键字

   使用sort对pair进行排序

3. sort
4. 双指针汇总
5. 蓝桥杯练习汇总