网易面试真题-瞌睡

一秉

小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的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
输出
16

实现代码：
import java.io.*;
import java.util.*;
   
public class Main {
      
    private static BufferedReader br;
    private static StreamTokenizer st;
    private static PrintWriter pw;
      
    final static int INF = 1000000007;
      
    static int[] getBit(int n) {
        int bit[] = new int[17];
        int cur = 0;
        while (n > 0) {
            bit[cur++] = n % 2;
            n >>= 1;
        }
        return bit;
    }
      
    static void solve() throws IOException {
        int n = nextInt();
        int k = nextInt();
        int a[] = new int[n];
        int b[] = new int[n];
        int t[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            t[i] = nextInt();
            b[i] = (i == 0 ? 0 : b[i - 1]);
            if (t[i] == 0) {
                b[i] += a[i];
            } else {
                ans += a[i];
            }
        }
        if (k > n) {
            pw.print(ans + b[n - 1]);
            return;
        }
        if (k == 0) {
            pw.print(ans);
            return;
        }
        int max = b[k - 1];
        for (int i = k; i < n; i++) {
            max = Math.max(max, b[i] - b[i - k]);
        }
        pw.print(max + ans);
    }
      
    public static void main(String args[]) throws IOException {
//        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
//        if (!oj) {
//            System.setIn(new FileInputStream("src/in.txt"));
//        }
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StreamTokenizer(br);
        pw = new PrintWriter(new OutputStreamWriter(System.out));
        st.ordinaryChar('\'');
        st.ordinaryChar('\"');
        st.ordinaryChar('/');
      
        long t = System.currentTimeMillis();
        solve();
//        if (!oj) {
//            pw.println("[" + (System.currentTimeMillis() - t) + "ms]");
//        }
        pw.flush();
    }
      
    static long pow(long a, long n, long mod) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans = (ans * a) % mod;
            }
            a = (a * a) % mod;
            n >>= 1;
        }
        return ans;
    }
      
    static void getDiv(Map<Long, Integer> map, long n) {
        long sqrt = (long) Math.sqrt(n);
        for (long i = sqrt; i >= 2; i--) {
            if (n % i == 0) {
                getDiv(map, i);
                getDiv(map, n / i);
                return;
            }
        }
        map.put(n, map.getOrDefault(n, 0) + 1);
    }
      
    private static String next(int len) throws IOException {
        char ch[] = new char[len];
        int cur = 0;
        char c;
        while ((c = (char) br.read()) == '\n' || c == '\r' || c == ' ' || c == '\t') ;
        do {
            ch[cur++] = c;
        } while (!((c = (char) br.read()) == '\n' || c == '\r' || c == ' ' || c == '\t'));
        return String.valueOf(ch);
    }
      
      
    private static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }
      
    private static long nextLong() throws IOException {
        st.nextToken();
        return Long.parseLong(st.sval);
    }
      
    private static double nextDouble() throws IOException {
        st.nextToken();
        return st.nval;
    }
      
    private static String[] nextSS(String reg) throws IOException {
        return br.readLine().split(reg);
    }
      
    private static String nextLine() throws IOException {
        return br.readLine();
    }
}