Java P5638 【CSGRound2】光骓者的荣耀

Java P5638 【CSGRound2】光骓者的荣耀

题目链接
思路：
暴力做法：两个for循环枚举所有情况，时间复杂度：O（n^2）;
前缀和：通过前缀和来压缩时间，使用一维for循环，时间复杂度：O(n)。
ps:前缀和与差分可以参考这篇文章
因为这个题目n最大为1e6，n^2的话妥妥的TLE，所以我们选择用前缀和来做。
其他细节看代码注释！

import java.util.*;
import java.io.*;
public class Main {
	
	static int N = 1000010;
	
	static long a[] = new long[N];
	static long s[] = new long[N];
	
	public static void main(String[] args) throws IOException {
		// 本题输入数据较大（一般以1e6的数据量为界），用Scanner会超时，所以用下面这种方法。
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer st = new StreamTokenizer(br);
		// nextToken：找到输入流中的下一个字段
		st.nextToken();
		// nval : 读取下一个字段，返回类型为Double，根据需要转为int或long类型。
		int n = (int)st.nval;
		st.nextToken();
		int k = (int)st.nval;
		
		
		for(int i = 1; i <= n - 1; i ++ ) {
			st.nextToken();
			a[i] = (long)st.nval; // a数组其实可以不用
			s[i] = s[i - 1] + a[i]; // 前缀和
		}
		
		long res = s[n - 1];
		if(k >= n - 1) res = 0;
		for(int i = 0; i + k <= n - 1; i ++ ) {
			res = Math.min(res, s[i] + s[n - 1] - s[i + k]);
		}
		System.out.println(res);
	}
}