牛客小白月赛86 --- E-- 可口蛋糕 ---- 题解

可口蛋糕

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小蓝制作了 n 个蛋糕并将其从左往右排成一行，其中第 i 个蛋糕的饱腹度为 wi 其可口值为 di。

由于手法过于生疏，尽管每个蛋糕的饱腹度必然为正数，但是可能存在蛋糕的可口值为负数！

作为可口蛋糕大赛的评委，小灰灰需要吃掉一段连续的蛋糕，使得蛋糕的饱腹度之和至少为 W。

而小蓝的得分就是小灰灰吃掉蛋糕所对应的可口值之和，她想知道在小灰灰帮助她的情况下，她的最大可能得分是多少。

输入描述:

第一行两个空格分隔的整数分别代表 n 和 W。接下来一行 n 个空格分隔的整数分别代表：w1,w2,...,wn。再接下来一行 n 个空格分隔的整数分别代表：d1,d2,...,dn。保证：
1≤n≤10^6

1≤W,wi≤10^9

0≤∣di∣≤10^9

W≤∑wi

输出描述:

输出一行一个整数代表答案。

示例1

输入

5 8
1 4 5 2 3
-1 -1 1 -2 1

输出

说明

选择区间 [2,3][2,3] 或者区间 [3,5][3,5] 时，这段蛋糕的饱腹度之和都超过了 8，且其可口值之和均为 0，可以证明这就是小蓝能够获得的最大得分。

思路解析：

因为他需要连续吃一段蛋糕，所以首先想到进行前缀和处理。

如果他一定要最后吃j这个蛋糕，那么它可以选择i开始吃，并且保证 j - i 这个区间的饱腹度大于等于w，对于一个j来说，他可能有多个可以选择的i，选择一个最优的i，是对于当前j位置的最佳答案，进行遍历每个可能的j位置，来求得最优答案。

代码实现：

import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {int n = input.nextInt();int m = input.nextInt();long[] a = new long[n + 1];long[] b = new long[n + 1];for (int i = 1; i <= n; i++) {a[i] = input.nextInt();}for (int i = 1; i <= n; i++) {b[i] = input.nextInt();}for (int i = 2; i <= n; i++) {a[i] += a[i - 1];b[i] += b[i - 1];}long ans = Long.MIN_VALUE;int i = 0;int j = 1;long mn = Long.MAX_VALUE / 2;while (j <= n && i <= n) {if (a[j] - a[i] >= m) {mn = Math.min(mn, b[i]);i++;} else {ans = Math.max(ans, b[j] - mn);mn =  Long.MAX_VALUE / 2;j++;}}System.out.println(ans);}static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static Input input = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}}