ACM 风格的 I/O 与内存管理
在算法竞赛（ACM）中，程序的执行效率至关重要。除了算法复杂度，I/O 和内存管理的开销也对性能有着决定性的影响。ACM 风格的编程追求极致的效率，其核心在于 I/O 缓冲 和 静态内存分配。

  1. 高效 I/O：BufferedReader 与 Scanner 的对比
    在 Java 中，Scanner 类提供了一个便利的接口，但其内部实现涉及频繁的底层 I/O 操作。每次调用 Scanner.nextInt() 或 Scanner.next()，都可能触发一次对系统 I/O 流的访问，这带来了显著的性能开销。

相比之下，BufferedReader 采用了一种缓冲机制来优化 I/O 性能。它在内存中维护一个缓冲区（默认大小为 8KB），并一次性从底层数据源（如 System.in）读取一大块数据。后续的读取请求都在这个内存缓冲区内完成，从而显著减少了对底层 I/O 设备的访问次数。

同样，为了优化输出，ACM 风格的程序会使用 PrintWriter 或 BufferedWriter，它们也利用缓冲区来批量处理输出数据，从而降低了系统调用的频率。

示例：使用 BufferedReader 高效读取数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class FastIOExample {
public static void main(String[] args) throws IOException {
// 创建一个“内存托管者”来处理输入
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 创建一个“内存托管者”来处理输出
PrintWriter out = new PrintWriter(System.out);

        // 一次性读取第一行，通常是数据量 n
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);

        // 读取包含所有数字的整行
        String[] data = br.readLine().split(" ");
        int[] arr = new int[n];

        // 从内存中快速解析并填充数组
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(data[i]);
        }
        
        // 在这里可以添加你的算法逻辑
        
        // 使用 PrintWriter 进行高效输出
        for (int i = 0; i < n; i++) {
            out.print(arr[i] + " ");
        }
        out.println();
        
        // 刷新缓冲区，确保所有内容都已输出
        out.flush();
    }
}
  1. 静态内存管理：避免动态分配开销
    在 Java 中，动态内存分配（使用 new 关键字）会涉及额外的开销，例如在堆上寻找合适的内存块。在数据量庞大或对象创建频繁的场景中，这种开销会累积并影响性能。

为了规避这一问题，ACM 风格的编程倾向于采用静态内存分配。在程序启动时，通过声明一个足够大的静态数组，预先在内存中分配好所需的全部空间。所有后续的数据存储和操作都在这个预分配的内存区域内进行，从而消除了运行时的动态分配开销。

  1. 示例：静态数组模拟邻接表
    静态内存分配的一个典型应用是在图论中，用数组来模拟邻接表。这种方法避免了 ArrayList 的动态扩容和频繁的对象创建。
import java.io.IOException;

public class Main {
private static final int N = 100010; // 节点数上限
private static final int M = 200010; // 边数上限

    private static int[] head = new int[N];
    private static int[] e = new int[M];
    private static int[] ne = new int[M];
    private static int idx;

    // 初始化邻接表
    public static void init() {
        for (int i = 0; i < N; i++) {
            head[i] = -1; // 初始化头指针为 -1
        }
        idx = 0;
    }

    // 添加一条从 a 到 b 的边
    public static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = head[a];
        head[a] = idx++;
    }

    public static void main(String[] args) throws IOException {
        init();
        // 在此处进行 I/O 操作和图的构建
        // 所有数据操作都在预先分配的静态数组上进行
    }
}