蓝桥杯日志统计

淡淡的烟草味﹌ 2022-03-10 10:08 188阅读 0赞

标题：日志统计
    小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：
    ts id 
    表示在ts时刻编号id的帖子收到一个"赞"。 
    现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。 
    具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。 
    给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。 
    【输入格式】
    第一行包含三个整数N、D和K。  
    以下N行每行一条日志，包含两个整数ts和id。 
    对于50%的数据，1 <= K <= N <= 1000  
    对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000 
    【输出格式】
    按从小到大的顺序输出热帖id。每个id一行。 
    【输入样例】
    7 10 2  
    0 1  
    0 10    
    10 10  
    10 1  
    9 1
    100 3  
    100 3 
    【输出样例】
    1  
    3 
    
    资源约定：
    峰值内存消耗（含虚拟机） < 256M
    CPU消耗  < 1000ms
    
    请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

import java.util.Arrays;
    import java.util.Scanner;
    
    class Main {
    	public static void main(String[] args) {
    		int n, d, k;
    		Scanner s = new Scanner(System.in);
    		n = s.nextInt();
    		d = s.nextInt();
    		k = s.nextInt();
    		Node arr[] = new Node[n];
    		for (int i = 0; i < n; i++) {
    			arr[i] = new Node(s.nextInt(), s.nextInt());
    		}
    		Arrays.sort(arr);
    
    		for (int i = 0; i < n; i++) {
    			System.out.println(arr[i].id + "-" + arr[i].ts);
    		}
    
    		for (int i = 0; i < n;) {
    			int j;
    			for (j = i + 1; j < n; j++) {
    				if (arr[i].id != arr[j].id) {
    					break;
    				}
    			}
    			int left = i, right = i;
    			int sum = 0;
    			while (left <= right && right <= j - 1) {
    				sum++;
    				if (sum >= k) {
    					if (arr[right].ts - arr[left].ts < d) {
    						System.out.println(arr[left].id);
    						break;
    					} else {
    						left++;
    						sum--;
    					}
    				}
    				right++;
    			}
    			i = j;
    		}
    	}
    }
    
    class Node implements Comparable<Node> {
    	int ts, id;
    
    	Node(int a, int b) {
    		ts = a;
    		id = b;
    	}
    
    	@Override
    	public int compareTo(Node o) {
    		// TODO 自动生成的方法存根
    		if (id == o.id) {
    			return ts - o.ts;
    		} else {
    			return id - o.id;
    		}
    	}
    
    }