【编程题】网易2019笔试：瞌睡

题目

小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。

输入描述

第一行 n, k (1 <= n, k <= 105) ，表示这堂课持续多少分钟，以及叫醒小易一次使他能够保持清醒的时间。
第二行 n 个数，a1, a2, … , an(1 <= ai <= 104) 表示小易对每分钟知识点的感兴趣评分。
第三行 n 个数，t1, t2, … , tn 表示每分钟小易是否清醒, 1表示清醒。

输出描述

小易这堂课听到的知识点的最大兴趣值。

示例
输入

6 3
1 3 5 2 5 4
1 1 0 1 0 0
1
2
3
输出

最初解题思路

把兴趣值和是否醒着储存到一个二维数组。
复制这个二维数组，按顺序修改数组，模拟每次被叫醒的状态，统计总兴趣值。
找出总兴趣值中的最大值，输出。

代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] scoremap = new int[n][2];
        for(int i = 0; i < n; i++){
            scoremap[i][1]=sc.nextInt();
        }
        for(int i = 0; i < n; i++){
            scoremap[i][0]=sc.nextInt();
        }
		//用于储存每种叫醒情况的总兴趣值
        int[] scores=new int[n];
        for(int i=0;i<n;i++){
	        //克隆原数组
            int scoremapClone[][] = new int[scoremap.length][];
            for(int j=0;j<scoremap.length;j++){
                scoremapClone[j]=scoremap[j].clone();
            }
            //模拟叫醒
            for(int j=0;j<k;j++){
                if(i+j<n){
                    scoremapClone[i+j][0]=1;
                }
            }
            //计算总兴趣值，并储存
            for(int j=0;j<n;j++){
                if(scoremapClone[j][0]==1){
                    scores[i]+=scoremapClone[j][1];
                }
            }
        }
        //找出最大值
        int max = Arrays.stream(scores).max().getAsInt();
        System.out.println(max);
    }
}

结果

AC 0.5 ，运行超时。
反思：克隆数组花费了大量时间，其实可以不模拟每次修改后的状态，只做实时运算。于是对代码做出改进。
其实每次的运算结果也不用都保存起来，最后再取最大值。只要保存一个当前最大值就可以了。

改进版思路

把兴趣值和是否醒着储存到一个二维数组。
实时计算每次叫醒可以获得的兴趣值，如果大于max（初始化为0）则储存到max。
加上固定兴趣值，输出结果。

改进版代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        int k= sc.nextInt();
        int[][] scoremap = new int[n][2];
        for(int i = 0; i < n; i++){
            scoremap[i][1]=sc.nextInt();
        }
        for(int i = 0; i < n; i++){
            scoremap[i][0]=sc.nextInt();
        }
        //最大兴趣值
        int max = 0;
        for(int i=0;i<n;i++){
            //储存当前叫醒可获得的兴趣值
            int cur = 0;
            //计算叫醒可以获得的兴趣值
            for(int j=0;j<k;j++) {
                if (i + j < n&& scoremap[i + j][0] == 0) {
                    cur += scoremap[i + j][1];
                }
            }
            //如果大于max则储存到max
            if(cur>max){
                max = cur;
            }
        }
        //加上固定兴趣值成为总兴趣值
        for(int j=0;j<n;j++){
            if(scoremap[j][0]==1){
                max+=scoremap[j][1];
            }
        }
        System.out.println(max);
    }
}

结果

AC 0.9 ，运行超时！！！

WTF!!!容老夫再想想。

想到的优化方式：

计算固定兴趣值这部分，其实可以在输入的同时计算，这样就少一个次数为N的循环。
（结果改了这个还是AC 0.9,于是又做出了下面的改进）
当宽度为n的滑动窗口超出k的范围时，所得到的兴趣值会逐渐减少。所以可以取消循环中（i>n-k+1）这部分。

最终版思路

其实和上面是一样的，不过从代码逻辑上和思路逻辑上分别减少了一些多余的操作。

最终版代码

import java.util.Arrays;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] scoremap = new int[n][2];
        //最大兴趣值
        int stable = 0;
        for(int i = 0; i < n; i++){
            scoremap[i][1]=sc.nextInt();
        }
        //在输入的同时储存固定兴趣值到max
        for(int i = 0; i < n; i++){
            scoremap[i][0]=sc.nextInt();
            if(scoremap[i][0]==1){
                stable+=scoremap[i][1];
            }
        }
        //最大兴趣值
        int max = 0;
        for(int i=0;i<n-k+1;i++){
            //储存当前叫醒可获得的兴趣值
            int cur = 0;
            //计算叫醒可以获得的兴趣值
            for(int j=0;j<k;j++) {
                if (i + j < n && scoremap[i + j][0] == 0) {
                    cur += scoremap[i + j][1];
                }
            }
            //如果大于max则储存到max
            if(cur>max){
                max = cur;
            }
        }
        System.out.println(max+stable);
    }
}

结果

AC 1.0。 NICE，此题完结。

总结

想想自己写的那个最初版代码真是

遇到题目不要总想着暴力破解。即使计算机性能强大，但实际上，当遇到某些输入量较大并且时间复杂度- 较高的程序，运行时间会明显增加。
一定尽量避免重复或者无效代码，可以实时运算的部分就不要占用储存空间。
对程序尽可能的优化，任意一点优化都可能对结果产生影响。
看到题目先在纸上画图分析一遍，对整理思路非常有帮助！
Java8中引入了Stream的概念，对于基本数值型，目前有三种对应的包装类型 Stream：IntStream、LongStream、DoubleStream。用Arrays.stream()方法可以获得一个Stream,本题第一个程序中使用了Stream.max()方法。关于Stream的更多使用可以看这里。给自己挖个坑= =