17 蓝桥真题：日志统计（附 IO 模板）

2018 Java B 组 T8. 日志统计

前言

「算法题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 17 篇题解，更多题解关注 Somnia1337@力扣。

分享最近刷的一些蓝桥杯 / CodeForces 题目，从「核心代码模式」逐渐转向、适应「ACM 模式」。

题目描述

本题目的在线练习：

https://www.dotcpp.com/oj/problem2279.html

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 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 一行。

「样例」

输入：

输出：

1
3

解题思路

按 id 分组记录每个帖子的时间戳，组内排序，双指针遍历，检查是否存在一个不长于 D 的窗口内至少有 K 次点赞。

复杂度

时间复杂度： $O (N lo g N)$ ，源于组内排序
空间复杂度： $O (N)$

代码

Java

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String... args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
		
        // 输入
        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        Map<Integer, List<Integer>> g = new HashMap<>(); // <id, 时间戳列表>
        while (N-- > 0) {
            st = new StringTokenizer(in.readLine());
            int ts = Integer.parseInt(st.nextToken()), id = Integer.parseInt(st.nextToken());
            g.computeIfAbsent(id, e -> new ArrayList<>()).add(ts);
        }
		
        // 处理
        List<Integer> ans = new ArrayList<>();
        for (Map.Entry<Integer, List<Integer>> e : g.entrySet()) {
            List<Integer> ts = e.getValue();
            int size = ts.size();
            if (size < K) continue; // 总赞数不足 K, 一定不行
            Collections.sort(ts); // 排序点赞时间
            int l = 0, r = 0; // 双指针
            while (r < size) {
                int R = ts.get(r++); // 右移 r
                while (l < r && ts.get(l) <= R - D) l++; // 左移 l 到窗口内
                if (r - l >= K) { // 窗口内点赞数至少为 K, 即符合要求
                    ans.add(e.getKey());
                    break;
                }
            }
        }
		
        // 输出
        Collections.sort(ans); // 要求按 id 递增顺序
        for (int x : ans) out.println(x);
		
        out.flush();
        out.close();
    }
}

IO 模板

创建 IO 对象

import java.io.*;
 
public class Main {
    public static void main(String... args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int T = Integer.parseInt(in.readLine()); // 很多题目会有 T 组数据
        while (T-- > 0) {
            // 处理每组数据
        }
        out.flush();
        out.close();
    }
}

读取一行的多个值

示例输入：2 行，第 1 行输入 n，第 2 行输入 n 个整数。

int n = Integer.parseInt(in.readLine()); // 第 1 行
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(in.readLine()); // 第 2 行
for (int i = 0; i < n; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
}

最后

更多系列「外源推文」&「生活分享」关注公众号：

🥑 EmberNecro

Explorer