教育改变生活

标题: 网易面试真题-瞌睡 [打印本页]

作者: 一秉 时间: 2020-6-28 09:44
标题: 网易面试真题-瞌睡
小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的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();
}
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)