算法题的ACM模式

简介

一般算法题有两种模式，比较熟悉的是lc的那种，你只需要实现一个核心方法，不用关心输入输出的部分。第二种模式就是这里介绍的ACM模式，这个模式下，全部的输入输出都要自己实现。有的面试会以第二种方式出题，需要熟悉一下，不要关键时刻不知道怎么处理。本文以java语言介绍一下ACM模式下应该如何写题接。

输入输出的相关方法

Java下，输入输出的方式分别对应Scanner和println

• 输入用nextXXX来取对应类型的数据，常用的就是int和nextLine
• 多个输入的情况下，再用for循环或者while里加入hasNext方法来遍历获取

  //输入
  Scanner in = new Scanner(System.in);
  int a = in.nextInt();
  String b = in.nextLine();
  boolean = in.nextBoolean();
  
  //输出
  System.out.println();

输入获取

首先明确，ACM模式下题目会对输入输出进行描述，比如输入会描述成下面的样子：

根据这个输入，就可以写对应的代码把输入中的值全部取出来

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 拿第一个int参数
        int n = in.nextInt();
       // 遍历剩下的每一行输入
        while (in.hasNext()) {
           String x = in.nextLine();
           System.out.println(x);
        }
    }
}

输出规则

和输入一样，输出也会有规则的描述

输出部分就比较简单了，根据描述，用sout进行打印就好

System.out.println(x);

总结

可以总结出下面这个ACM代码提交的模版，其中嵌入真正核心的解题函数即可

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 参数获取
        int n = in.nextInt();
        //此处一定要用nextLine换行！！！，否则会读到一个空行
        in.nextLine();
        List<String> list = new ArrayList<String>();
        while (in.hasNext()) {
           list.add(in.nextLine());
        }
        // 真正的解题函数，和lc中一致
        List<Integer> res = getRes(n, list);
        //输出部分
        for(int i: res){
          System.out.println(i);
        }
    }
    public List<Integer> getRes(int n, List<String> list){
      ...
    }
}

拓展

定义类

如果题目需要自定义类，则直接在Main类的外面下面加，但注意：不要写public的类，java中public的类必须定义在一个同名的文件中。

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
       // 读参数。。。。
        Node n = new Node(1,1);
    }
}
class Node {
    int a;
    int b;
    public Node(int a, int b) {
        a = a;
        b = b;
    }
}

摆脱解题函数的束缚

ACM方式其实更灵活，上面模版是标准的写法，即获取输入，传入解题函数，打印解题函数的返回值。

但实际上可以直接在main函数中做相关的操作，有时候会更快，比如每一行输入能得到对应的一个输出，这种情况下就不需要等全部输入都读完，读一行就能处理一行了。

一个坑

在使用了nextInt方法之后，扫描器的指针其实还是在这一行的，因为还有一个换行符没有读到。此时应该再调用一下nextLine方法，真正切换到下一行。