小白题解

1 暴力

(通过 6/11 讨分嘛 不寒碜 )

最容易想到的暴力解法
第一层循环是 时间 0到最大时间
第二层循环是 所有的id 判断它的时刻是否属于要求的长度的时间区间
是的话就统计它的次数 +1
然后判断一下它的次数是否已经>k 是的话将布尔数组它的位置 置为true
然后再每次判断新的时间区间时 要将cnt初始化为全0

C++ 代码

#include <bits/stdc++.h>
#define ts first
#define id second
using namespace std;

const int N = 1e5+10;
typedef pair<int,int> pii;
pii blog[N];
bool hot[N];
int cnt[N];
int n,d,k;

int main(){
    scanf("%d%d%d",&n,&d,&k);
    int maxt = 0;
    for(int i = 1;i<=n;i++)
            {
                scanf("%d%d",&blog[i].ts,&blog[i].id);
                maxt = max(blog[i].ts,maxt);
            }

    for(int time = 0;time <= maxt; time++)
    {
    memset(cnt,0,sizeof(cnt));
    for(int i = 1;i<=n;i++)
    {
        int t = blog[i].ts;
        int id = blog[i].id;
        if( t >= time && t <time+d)
            cnt[id]++;
        if(cnt[id] >= k)
            hot[id] = true;
    }
    }
    for(int i = 0;i<=1e5;i++)
    if(hot[i]) printf("%d\n",i);

}

双指针优化

因为其实在求某段时间区间内的数量时
前一区间和后一区间有大部分是存在重复的
我们要做的就是利用这部分 来缩短我们查询的时间
并且在使用双指针时要注意对所有的博客记录按时间从小到大先排好顺序
因为在有序的区间内才能使用双指针记录两个区间相差
相当于把一个有序的时间序列进行每次递增1的划分
所以 这里我用划分来理解这里所用的双指针
也就是不能把双指针看作是在所有数据内访问
应该是在一个个被细分的符合要求的时间区间内访问
而while循环做的工作就是将这个区间进行归位
若i前移过程超出了时间区间D j就向前移 找到符合要求的下一个区间位置
并且要退回之前的cnt
也就是在while循环里 先执行cnt[j]– 再进行j 前移
因为要执行j 说明之前的j已经不在下一个区间了
因为j已经追随i到了下一个区间了
所以这个j位置对应的id的赞数就不符合D的时间区间要求了，要执行cnt[j]–
相当于 暴力做法里面的 memset 执行cnt 初始化为全0

上个图片 因为我看别的题解实在有点没理解 所以模拟了一下…菜是原罪
可能除了我自己 也没谁能看懂了把.....

hmm 代码就是那样.....

#include <bits/stdc++.h>
#define ts first
#define id second
using namespace std;

const int N = 1e5+10;
typedef pair<int,int> pii;
pii blog[N];
bool hot[N];
int cnt[N];
int n,d,k;

int main(){
    scanf("%d%d%d",&n,&d,&k);

    for(int i = 0;i<n;i++) //因为要用到sort  所以下标从0 开始
        scanf("%d%d",&blog[i].ts,&blog[i].id);

    sort(blog,blog+n);

    for(int i = 0,j = 0; i < n;i++)
    {
        int bid = blog[i].id;
        cnt[bid]++;
        while(blog[i].ts - blog[j].ts >= d)
        {
            cnt[blog[j].id]--;
            j++;
        }
        if(cnt[bid] >= k) hot[bid] = true;
    }

    for(int i = 0;i<=1e5;i++)
        if(hot[i]) printf("%d\n",i);
}