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

题目：1238. 日志统计

日志就是记录
暴力解法：

先for循环多个时间段
循环每个时间段内每个帖子被点赞的数量
如果帖子的数量大于等于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 secondusing 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;
}

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

相关链接：