AcWing 1238. 日志统计

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1238. 日志统计原题链接中等

作者：

大海呀大海 , 2020-07-10 20:17:11 , 所有人可见 , 阅读 10717

197

38

双指针算法

#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];//用来标记id号，因为id <= 1e5，所以可以利用遍历来输出。
int cnt[N];//用来记录一个id号获得的赞数，表示形式为cnt[id]++;

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);
    //排序时默认以first为准排序
    sort(logs, logs + n);

    //双指针算法， i走在前面，j走在后面
    for (int i = 0, j = 0; i < n; i ++ ){
        int t = logs[i].y;//t表示为i时刻的id号
        cnt[t] ++;//在j时刻，id号为t的大佬日记获得了一个赞，给t大佬加一分

        while (logs[i].x - logs[j].x >= d){//两个指针跨越的时间超过了d，早期的赞过期了
            cnt[logs[j].y] --;//就是这位大佬，获赞的时间太久远了，赞作废了，哭去吧
            j ++;//在logs[j].x时刻的太久远了，往前挪挪。
            //这个循环，直到最后一个赞不过期为止。
        }
        //记录热帖的id号，好知道谁才是大佬
        if (cnt[t] >= k) st[t] = true;
    }

    //遍历一遍id号，展现大佬
    for (int i = 0; i <= 100000; i ++ ) if (st[i]) cout << i << endl;

    return 0;
}

61 评论

Showball 2023-02-23 17:24

有趣的刷题生活从看到这篇有趣的题解开始~

Acxxxqq 2023-03-11 11:05

这里的i时刻和j时刻应该不是准确的说法思路是利用i和j遍历日志，因为时间是从小到大排序的，所以让j从头开始，不断遍历i下标的日志，如果j和i指向的时间差大于D了就让j移动直到满足时间差的关系，而移动j势必有日志要移出区间，于是先删再移这里可以思考一下while循环和最后if判断的顺序问题可以帮助更好的理解过程

18735996583 2023-03-26 11:02

while (logs[i].x - logs[j].x >= d)我不理解他是怎么确定 i 和 j 的id相同

Acxxxqq 2023-03-28 16:10 回复了 18735996583 的评论

i和j的id不需要相同。你首先得知道他是如何枚举的。它是枚举每个时间段，在符合条件的时间段里，说白了就是小于等于d的时间段里，去统计每个id的数量，如果一个id的数量大于k,就是热帖。由于时间段是不断向后枚举的，所以当时间段大于了d，就必须抛弃原时间段开头的那个元素，因此有这句代码：cnt[logs[j].y] –; ~~~ 半个月没刷题了今天开始复习蓝桥杯冲冲省二

汩潨 2024-02-27 21:39

大佬我似乎终于懂了

无聊就睡觉 2025-02-11 17:17 回复了 Acxxxqq 的评论

我觉得这里t一次循环只能确定一个id啊，万一有那种同一时刻很多id点赞的情况，他这样不会错过别的id吗？因为i直接++了到下一时刻。大佬能解答一下吗…

夏目_2 2025-04-06 22:18 · 湖南回复了无聊就睡觉的评论

我理解的是，因为按照时间排序的日志，并且D相同，现在的时间段如果不满足遍历到的日志时间的话，那前面的也过了有效时间，可以舍弃。如果前面的有某个id到了点赞数k，而i是从前面每个日志遍历来的，在遍历那个日志的时候肯定被统计过了，所以是可以用双指针的。你说的同一时刻很多id，那i和j指向的时间段是不变的吧

无聊就睡觉 2025-04-08 17:25 · 湖北回复了夏目_2 的评论

谢谢，当时没看懂，过了一段时间再看，一下就通了。

xiao菜b一个 2024-03-06 00:29

#### 贴一个单调队列的。

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
const int N = 100010;

int n, d, k;
int q[N], hh = 0, tt = -1;
int zhan[N];
PII ts[N];
set<int> res;

int main()
{
    cin >> n >> d >> k;
    for(int i = 0; i < n; i ++)
        cin >> ts[i].first >> ts[i].second;

    sort(ts, ts + n);

    //遍历所有点赞的帖子
    for(int i = 0; i < n; i ++)
    {
        while(ts[q[hh]].first <= ts[i].first - d && hh <= tt){
            hh ++;
            zhan[ts[q[hh]].second] --;
        }
        zhan[ts[i].second] += 1;
        if(zhan[ts[i].second] >= k) res.insert(ts[i].second);
        q[++tt] = i;
    }
    for(auto i : res) cout << i << endl;

    return 0;
}

晨曦遇晓 2024-03-21 21:28

你这个过不了啊

xiao菜b一个 2024-03-22 15:29 回复了晨曦遇晓的评论

我的电脑可以过的

Ødegaard 2024-04-04 21:28 回复了 xiao菜b一个的评论

你说的好好笑

xiao菜b一个 2024-04-06 09:22

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
const int N = 100010;

int n, d, k;
int q[N], hh = 0, tt = -1;
int zhan[N];
PII ts[N];
set<int> res;

int main()
{
    cin >> n >> d >> k;
    for(int i = 0; i < n; i ++)
        cin >> ts[i].first >> ts[i].second;

    sort(ts, ts + n);

    //遍历所有点赞的帖子
    for(int i = 0; i < n; i ++)
    {
        while(ts[q[hh]].first <= ts[i].first - d && hh <= tt){
            zhan[ts[q[hh ++]].second] --;
        }
        zhan[ts[i].second] += 1;
        if(zhan[ts[i].second] >= k) res.insert(ts[i].second);
        q[++tt] = i;
    }
    for(auto i : res) cout << i << endl;

    return 0;
}

上面那个hh++不应该单独列出来，应该从hh开始。现在这个是对的

摇曳 2023-02-02 13:13

感谢大佬，注释也很可爱

Jonny_6 2025-03-25 15:19 · 山东

#include<bits/stdc++.h>
#define PII pair<int,int>
#define id first
#define t second
using namespace std;
const int N = 100005;
int n,d,k;
PII p[N];
bool vis[N];

int main()
{
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++) cin>>p[i].t>>p[i].id;
    sort(p+1,p+n+1);
    for(int i=1,j=1;i<=n&&j<=n;i++){
        if(vis[p[i].id]) continue;
        while(p[i].id!=p[j].id&&j<i) j++;
        while(p[i].t-p[j].t+1>d&&j<i) j++;
        if(p[i].t-p[j].t+1<=d&&i-j+1>=k&&!vis[p[i].id]){
            cout<<p[i].id<<endl;
            vis[p[i].id]=true;
        }
    }
    return 0;
}

汩潨 2024-03-06 20:58

为什么foe循环里面是while循环而不是if判断呀

continue_8 2024-03-27 20:58

每个i都需要通过起始的j不断移动来判断

tobetheonly 2024-03-05 22:27

为啥过不了啊

#include<bits/stdc++.h>
using namespace std;
//1238 日志统计
const int N=1e5+10;
int n,d,k;
multiset<int>se;//存某个区间某个id出现的次数
map<int,int> mp;//存在几个区间符合要求
struct Range
{
    int ts,id;
    bool operator<(const Range &W)
    {
        return ts<W.ts;
    }
}rang[N];
int main()
{
   cin>>n>>d>>k;
   for(int i=0;i<n;i++)
   {
       int t,id;
       cin>>t>>id;
       rang[i]={t,id};
   }
   sort(rang,rang+n);

   int i=0,j=0;
   while(i<n)
   {

       //走一个区间
      while(rang[j].ts<rang[i].ts+d&&j<n)
      {
         int t=rang[j].id;
         j++;
         se.insert(t);
         if(se.count(t)>=k)
         {
            mp[t]++;
         }
      }
      se.clear();
      i=j;
   }
   for(auto t=mp.begin();t!=mp.end();t++)
   {
        if(t->second)
          cout<<t->first<<endl;
   }


}

Fool_one 2021-03-30 22:12

注释里应该是在 i 时刻

永远少年_3 2025-04-05 19:55 · 江苏

这里是一些关于不懂为什么只用j就能实现维护区间的一些解释，希望给大家提供帮助
https://www.acwing.com/solution/content/276107/

十二块曲奇 2024-04-09 11:39

这题能否用滑动窗口来实现呢？

稗官 2024-04-11 09:58

这不就是滑动窗口吗

言笑_3 2024-04-03 21:39

懂啦！谢谢大佬好生动的注解

Ba_6 2024-03-25 21:35

#include[HTML_REMOVED]

using namespace std;

int main() {
int N, D, K;
cin >> N >> D >> K;

unordered_map<int, vector<int>> likes; // 记录每个帖子在每个时刻的点赞数

for (int i = 0; i < N; i++) {
    int ts, id;
    cin >> ts >> id;
    likes[id].push_back(ts); // 更新帖子的点赞数
}

vector<int> hot_posts; // 记录曾是热帖的帖子编号

for (auto& p : likes) {
    vector<int>& timestamps = p.second;
    sort(timestamps.begin(), timestamps.end()); // 将时间戳按升序排序
    int left = 0, right = 0; // 左右指针，表示时间段的左右边界
    int count = 0; // 计数器，统计点赞数
    while (right < timestamps.size()) {
        // 计算当前时间段内的点赞数
        if (timestamps[right] - timestamps[left] < D) {
            count++;
            right++;
        } else {
            // 如果时间段超过了 D，则移动左指针
            count--;
            left++;
        }
        // 如果当前时间段内的点赞数达到了 K，则该帖子是热帖
        if (count >= K) {
            hot_posts.push_back(p.first);
            break;
        }
    }
}

sort(hot_posts.begin(), hot_posts.end()); // 对热帖编号进行排序

for (int id : hot_posts) {
    cout << id << endl; // 输出热帖编号
}

return 0;

}

莫比乌斯_4 2024-03-19 11:02

看起来就是滑动窗口

cypher 2024-03-12 11:42

哈希表存储遍历时间

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;


const int N = 100010;

int n, d, k;
int t[N];
int cnt[N];

int main() {
    vector<vector<int>> hash(N);
    scanf("%d%d%d", &n, &d, &k);
    int len = 0;
    for (int i = 0 ;i < n; i ++) {
        int t, id;
        scanf("%d%d", &t, &id);
        hash[t].push_back(id);
        len = max(len, t);
    }
    set<int> s;
    for (int l = 0, r = 0; r <= len; r ++) {
        for (int j = 0; j < hash[r].size(); j ++) {
            int id = hash[r][j];
            //cout << id << endl;
            cnt[id]++;
            if (cnt[id] >= k) s.insert(id);
        }
        while (r - l + 1 >= d) {
            for (int j = 0; j < hash[l].size(); j ++) {
                int id = hash[l][j];
                cnt[id]--;
            } 
        l ++;
        }
    }
    for (auto it = s.begin(); it != s.end(); it ++) {
        printf("%d\n", *it);
    }
    return 0;

}

cypher 2024-03-12 11:43

看上去两层循环，时间复杂度应该是o（n），就是把所有事件都遍历了两遍

._1322 2024-03-03 21:21

大佬帮忙看看，为什么用加法过不了这题啊
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N=1e5+10;
int n,d,k;
int cnt[N];
bool st[N];
#define ts first
#define id second
pair[HTML_REMOVED]g[N];
int main()
{
scanf(“%d%d%d”,&n,&d,&k);
for(int i=1;i<=n;i)
{
scanf(“%d%d”,&g[i].ts,&g[i].id);
}
sort(g+1,g+n+1);//直接对时间进行排序，然后只统计在这段时间内每种id的点赞数就行了
printf(“排序后\n”);
for(int i=1;i<=n;i)
{
printf(“%d %d\n”,g[i].ts,g[i].id);
}
for(int i=1,j=1;i<=n;i)
{
memset(cnt,0,sizeof cnt);
printf(“gg\n”);
while(g[j].ts-g[i].ts[HTML_REMOVED]= k) st[g[j].id] = true;
j;
}
if (cnt[g[j].id] >= k) st[g[j].id] = true;
}

for (int i = 0; i < 100010; i++)
    if (st[i]) 
        printf("%d\n", i);


return 0;

}

xiao菜b一个 2024-03-06 00:30

你把你代码放到两组三个点之间，就能格式化显示

hanhyojoo 2023-11-28 21:45

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second 
const int N=100010;
typedef pair<int,int>  PII;
int n,d,k,res,sum[N];
PII p[N];
bool q[N];

int main() {

    cin >> n >> d >> k;
    for (int i = 1; i <= n; i++)
    {
    scanf("%d %d",&p[i].y,&p[i].x);
        sum[p[i].x]++;
    }
    sort(p + 1, p + n + 1);
    for (int i = 1, j = 1; i <= n;)
    {
        res = 0;
        if (sum[p[i].x] >= k && !q[p[i].x])
        {
            while (p[i].x==p[j].x&&j <= n && p[j].y - p[i].y <= d - 1)
            {
                res++;
                if (res == k)
                {
                    q[p[i].x] = true;
                  printf("%d\n",p[i].x);
                    break;
                }
                j++;
            }
        }
         j=++i;
    }

    return 0;
}