Java算法必备（背）之快读快输出

总所周知，使用Java在算法中是比别的语言低一等 比使用别的语言更加快乐，你可以wa得更多更莫名其妙 学到更多东西。所以在读入方面，Java理所当然是更加鸡肋 更加需要技巧。

为什么要使用快读快输出？

在绝大多数时候，我们读入数据都是用Scanner类读入，简单熟练，可是当数据比较大的时候（个人经验，洛谷数据过万，PTA数据过两千，建议使用快读），我们快读主要是使用io包的StreamTokenizer类。当数据的数量级为10^5时，用StreamTokenizer类差不多好像是要比Scanner快个300ms左右

这个时间虽然感觉非常短！！很难察觉到差别， 但是在算法实现中300ms 已经是一个非常大的数字了，它极有可能让你在TLE和AC之间无限试探。

快输出用的是io包的PrintWriter类，它比常规的输出也是快不少的，也是AC的一大法宝

言归正传，我们开始进入今天的正题~

StreamTokenizer类和PrintWriter类的介绍

StreamTokenizer类
StreamTokenizer类接收输入流并将其解析为“令牌”，允许一次读取一个令牌。 解析过程由表和多个可以设置为各种状态的标志来控制。 流标记器可以识别标识符，数字，引用的字符串和各种注释样式。
从输入流读取的每个字节被视为’\u0000’至’\u00FF’范围内的’\u0000’ ‘\u00FF’ 。 字符值用于查找字符的五个可能属性： 空格 ， 字母 ， 数字 ， 字符串引号和注释字符 。 每个角色都可以有零个或多个这些属性。
注意：使用StreamTokenizer类要记得抛出I/O异常

PrintWriter类
将对象的格式表示打印到文本输出流。 这个类实现了全部在发现print种方法PrintStream 。 它不包含用于编写原始字节的方法，程序应使用未编码的字节流。
不像PrintStream类，如果启用自动刷新，它只会在调用的println，printf，或format方法来完成，而不是当一个换行符恰好是输出。 这些方法使用平台自己的行分隔符而不是换行符。

这个类中的方法不会抛出I / O异常，尽管它的一些构造函数可能。 客户可以通过调用checkError()查询是否发生错误。

StreamTokenizer类的使用

下面简单介绍一下StreamTokenizer类的注意事项
（1）我们在使用StreamTokenizer类时，我们要导入io包，它是io包中的类
（2）在使用这个类时，函数要抛出IOException异常（throws IOException）
（3）每一次读入之前都要用nextToken（）方法获取下一个数据
（4）读取数据的方法，sval方法读取字符串类型（以空格或者换行分隔），nval方法读取数字类型数据。读取字符串类型的数据时，一次只能读一个字符串，读取数字类型的数据时，默认为double类型
（5）StreamTokenizer类使用的具体写法

import java.io.*;
public class test {
	public static void main(String args[]) throws IOException{
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); 
		st.nextToken();
		String str = st.sval;//读取String类型数据
		st.nextToken();
		double num1 =  st.nval;//读取double类型数据
		st.nextToken();
		int num2 = (int)st.nval;//读取int类型数据
		st.nextToken();
		long num3 = (long)st.nval;//读取long类型数据
	}
}

在这里我们可以看到，我们每读一个数据就要用一次 nextToken（）方法。这个方法是我们每次读入数据之前必须要写的，也就是我们读入一个数据之前就要写一个这个方法才行

如果我们只想读字符串怎么办？
当我们只读字符串的时候我们就不需要加StreamTokenizer类
我们可以直接写成 BufferedReader br = new BufferedReader(new InputStreamReader(System.in))；

import java.io.*;
public class test {
	public static void main(String args[]) throws IOException{
//		StreamTokenizer re = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
		String x = re.readLine();
		System.out.println(x);
	}
}

当我们使用这种方法的时候就可以一次性读取一大串带空格的字符串了，而且还不用和前面一样，每读一次就使用一次 nextToken（）方法

PrintWriter类的使用

PrintWriter类的使用相对而言比较简单，就是把我们平时的输出的System.out替换成对应的快输出的实例对象名，唯一需要比较注意的就是最后记得flush()

代码如下：

import java.io.*;
public class test {
	public static void main(String args[]){
		PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
		pw.print();//不换行输出
		pw.println();//换行输出
		pw.printf();//格式化输出
		pw.flush();//关闭输出流
	}
}

来个例子，玩一下

题目链接奉上：
P5638 【CSGRound2】光骓者的荣耀
这一道题是一道相当经典的快读题，虽然是入门题，可是不用快读的话，用Java无论你怎么优化都过不了，恶心至极 实在是太有意思了。（一个同学孜孜不倦的优化了三四十次，wa了三四十次）

每当被Java读数据恶心到 需要使用快读时我就会想起这张照片，说实话有点招恨。

由于小K的不稳定传送器只能传送一次，可以想到用总时间-传送节约的跑的时间

因为总距离是变不了的，所以说求出传送节约时间的最大值即可求出最短需要的时间

如果一个一个枚举的相隔k的城市之间的时间的话，会很慢，于是想到用一个求区间和的好东西：前缀和

前缀和通常用sum[ ]表示，sum[i]表示从1到i之间的总和（这里就是从1跑到i所需的时间），用前缀和求从a地跑到b地所需的时间，求sum[b]-sum[a]即可

这样，找出相距k的点之间跑的时间的最大值就用一遍for就可以过了

并且用前缀和的话，sum[n]就是所要求的总距离

于是问题就解决了

常规代码：

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);		
		int n = in.nextInt();//读入城市数量
		int k = in.nextInt();//读入传送半径
		long[] arr = new long[n];//存储连续两点的距离
		long[] sum = new long[n];//存储前面n个点的距离和
		for (int j = 1; j < n; j++) {//读入计算具体距离
			arr[j]=in.nextLong();
			sum[j]=sum[j-1]+arr[j];
		}
		
		long ans=0;
		for (int j = k; j <= n-1; j++) {//查找最大距离区间
			if(ans<sum[j]-sum[j-k]) {
				int t=j-k;
				ans = sum[j]-sum[j-k];
			}
		}
		System.out.println(sum[n-1]-ans);//输出总距离减去最大距离区间
	}
}

感人的MLE～^～

快读代码

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException  {
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int)in.nval;
        in.nextToken();
        int k =(int)in.nval;
		long[] arr = new long[1000000];
		long[] sum = new long[arr.length];
		for (int j = 0; j < n-1; j++) {
            in.nextToken();
			arr[j]=(long)in.nval;
		}
		
		for (int i = 1; i < n; i++) {
			sum[i]=sum[i-1]+arr[i-1];
		}
		
		long ans=0;
		for (int j = k; j <= n-1; j++) {
			if(ans<sum[j]-sum[j-k]) {
				ans = sum[j]-sum[j-k];
			}
		}
		System.out.println(sum[n-1]-ans);
	}
}

完美AC

结束了，撒花～～～～～

感谢你的阅读，欢迎留言交流，如有错误，请不吝赐教。谢谢！