当前位置: 代码迷 >> 综合 >> 【蓝桥杯练习--双指针】1238.日志统计
  详细解决方案

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

热度:21   发布时间:2024-02-23 08:05:49.0

题目: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 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;
}

相关链接:

  1. memset
  2. pair
    将两个属性值放在一起构成一个新的结构体类型(类似stl中的map 是将value和key结合起来)
    因为是结构体,所以可以直接访问其中的变量
    排序时会首先根据第一关键字进行排序,然后根据第二关键字
    使用sort对pair进行排序
  3. sort
  4. 双指针汇总
  5. 蓝桥杯练习汇总