日志统计(每日一题)

秒速五厘米 2024-03-30 17:07 76阅读 0赞

## 日志统计 ##

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格式是：

ts id  
表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 \[T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式  
第一行包含三个整数 N,D,K。

以下 N 行每行一条日志，包含两个整数 ts 和 id。

输出格式  
按从小到大的顺序输出热帖 id。

每个 id 占一行。

数据范围  
1≤K≤N≤105,  
0≤ts,id≤105,  
1≤D≤10000  
输入样例：  
7 10 2  
0 1  
0 10  
10 10  
10 1  
9 1  
100 3  
100 3  
输出样例：  
1  
3

提交代码：  
C++

#include<bits/stdc++.h>
    using namespace std;
    
    #define x first
    #define y second
    typedef pair<int, int> PII;
    const int N = 100010;
    int n, d, k;
    int cnt[N];
    PII logs[N]; // 存放每时刻的点赞情况
    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);
        for (int i = 0, j = 0; i < n; ++ i)
        {
        
            int id = logs[i].y; // 这个时刻这这个id被点赞了
            cnt[id] ++; // 然后这个人对应的cnt++
            while(logs[i].x - logs[j].x >= d) // 如果区间【j, i】长度大于等于d
                                              // 就需要把前面多余的区间的cnt--
            {
        
                cnt[logs[j].y] --; // 把前面加了的再减回来
                j ++;
            }
            if (cnt[id] >= k) st[id] = true; // 如果在不大于d区间以内可以满足要求 则为true
        }
        for (int i = 0; i <= 100000; ++ i)
        {
        
            if(st[i]) printf("%d\n", i); // 因为这里的id的范围说出来了 所以可以一个个看 那些符合要求
        }
        return 0;
    }

Java

import java.util.*;
    import java.io.*;
    
    public class Main
    {
        
    	static int N = 100010;
    	static int n, d, k;
    	static int [] cnt = new int [N];
    	static PII [] logs = new PII [N];
    	static boolean [] st = new boolean [N];
    	public static void main(String[] args) throws IOException
    	{
        
    		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    		String [] strs = reader.readLine().split(" ");
    		n = Integer.parseInt(strs[0]);
    		d = Integer.parseInt(strs[1]);
    		k = Integer.parseInt(strs[2]);
    		for (int i = 0; i < n; ++ i)
    		{
        
    			strs = reader.readLine().split(" ");
    			int t = Integer.parseInt(strs[0]);
    			int id = Integer.parseInt(strs[1]);
    			logs[i] = new PII(t, id);
    		}
    		Arrays.sort(logs, 0, n);
    		for(int i = 0,j = 0;i < n;i++)
           {
        
               cnt[logs[i].id] ++;
               while(logs[i].t - logs[j].t >= d)
               {
        
                   cnt[logs[j].id] --;
                   j ++; // 先减了之后才能++
               }
               if(cnt[logs[i].id] >= k) st[logs[i].id] = true; 
           }
    		for(int i = 0; i <= 100000; ++ i)
    		{
        
    			if (st[i]) System.out.println(i);
    		}
    	}
    	
    	public static class PII implements Comparable<PII>
    	{
        
    		int t;
    		int id;
    		public PII (int t, int id)
    		{
        
    			this.t = t;
    			this.id = id;
    		}
    		@Override
    		public int compareTo(PII o) {
        
    			// TODO Auto-generated method stub
    			return Integer.compare(t, o.t);
    		}
    		
    	}
    }

Python

N = 100010
    
    if __name__ == '__main__':
        n, d, k = map(int, input().split())
        logs, cnt, st = [], [0]*N, [0]*N
        for _ in range(n): logs.append([int(x) for x in input().split()])
        logs.sort()
    
        i, j = 0, 0
        while i<n:
            ts, id = logs[i]
            cnt[id] += 1
            while ts-logs[j][0]>=d:
                cnt[logs[j][1]] -= 1
                j += 1
            if cnt[id]>=k: st[id] = 1
            i += 1
    
        for i in range(N):
            if st[i]: print(i)