竞争性编程和输入

Question

我正在为几周后在我的学院举行的竞技比赛进行练习，因此我遇到了一个小问题。
比赛限制了java.io的使用。*（IOException除外...）
我需要（从标准输入）读取输入，每个测试用例都用空行分隔。测试用例结束 - 当发现 EOF 时。
我需要找到一种从 IO 获取数据的方法，而不使用 java.io
到目前为止，我得到了这个（有效） - 它返回一个包含每个测试用例的字符串，当我没有测试用例时返回 null。

public static String getInput() throws IOException {
    int curr=0;
    int prev=0;
    StringBuilder sb = new StringBuilder();
    while (true) {
        curr = System.in.read();
        if (curr == -1) { 
            return null; //end of data
        }
        if (curr == '\r') {
            curr = System.in.read();
        }
        if (curr == prev && curr == '\n') {
            return sb.toString(); //end of test case
        } //else:
        sb = sb.append((char)curr);
        prev = curr;
    }
}

性能（对于IO）被忽略了，所以我不在乎每次只读取一个字节。
问题：是否有更优雅（编码更短、速度更快）的方法来实现相同的目标？

Answer 1

事实上，在竞争性编程中，有几种方法可以处理 Java 中的输入。

方法 1：使用 java.util.Scanner

这是读取输入的最简单方法，而且使用起来也非常简单。如果您有大量输入，速度可能会很慢。如果您的程序不断获得 TLE（超出时间限制），但您的程序具有正确的时间复杂度，请尝试使用第二种或第三种方法读取输入。

初始化 Scanner sc = new Scanner(System.in);

读取整数：int n = sc.nextInt();
方法 2：使用 java.io.BufferedReader

如果输入量很大并且问题的时间限制很严格，请使用此方法。它确实需要更多的工作，包括按空格分割输入，或使用 Integer.parseInt(str); 来从输入中提取整数。

您可以在此处找到速度比较 https://www.cpe。 ku.ac.th/~jim/java-io.html

初始化： BufferedReader reader = new BufferedReader(System.in);

读取整数： int n = Integer.parseInt(reader.readLine());

方法 3：使用自定义读取器直接从 FileDescriptor 读取

这种方法是Java 中可能的最快方法。它确实需要大量工作，包括实现阅读器，以及在出现任何问题时进行调试。如果时间限制严格并且允许您将代码带入竞赛，请使用此方法。经测试，此方法比第二种方法快得多，但它通常不会为您提供优势，因为它的速度仅为 BufferedReader 方法的大约 2 倍。

这是我的朋友编写的这种方法的一个实现：
https://github.com/jackyliao123/contest-programming/ blob/master/Utils/FastScanner.java

读取器的使用实际上取决于您的读取器的实现。建议保留一份可以保证正常工作的阅读器副本，因为在竞赛中您最不想看到的就是拥有一个无法正常工作的阅读器并调试程序的其余部分，认为那里存在一些错误。

希望这对您有所帮助，并祝您比赛顺利！

Answer 2

您可以尝试以下方法，并通过包装 System.in 来提高效率。

public static String readLine() throws IOException {
    StringBuilder sb = new StringBuilder();
    for (int ch; (ch = System.in.read()) > 0;)
        if (ch == '\r') continue;
        else if (ch == '\n') break;
        else sb.append(ch);
    return sb.toString();
}

编辑：在Oracle JVM上，System.in是一个BufferedInputStream，它包装了一个FileInputStream，而FileInputStream又包装了一个FileDescriptor。所有这些都在java.io中。

Answer 3

如果允许 java.util，您可以尝试使用 java.util.Scanner 类。它有一些有用的方法可以根据需要读取一行、一个标记甚至一个数字。但它比 BufferedReader 慢，并且可能比直接使用 System.in.read() 慢。

由于 System.in 实现了 InputStream 接口，因此使用 System.in.read(byte[] b) 也可能会提高速度读入输入。这样，您可以一次读取一堆字节，而不是只读取一个字节，这应该会更快。但在比赛期间必须编码和调试所增加的复杂性可能不值得。

编辑：
在网上搜索时，我发现有人在 UVa 论坛 那时 UVa 对 Java 的支持很糟糕。

Answer 4

您可以使用扫描仪

import java.util.Scanner;//put this above the class
Scanner scanner = new Scanner(System.in); //this creates the scanner
int input = scanner.nextInt();

.nextInt() 接受整数
.nextLine() 接受字符串