携程笔试第四题为什么0分?
import java.io.*; import java.util.ArrayDeque; import java.util.Deque; public class Main { private static long n, k, sum, intervalSum, res; private static final int N = 100010; private static long[] a = new long[N], s = new long[N]; private static Deque<Long[]> q = new ArrayDeque<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] in = br.readLine().split(" "); n = Long.valueOf(in[0]); k = Long.valueOf(in[1]); sum = Long.valueOf(in[2]); in = br.readLine().split(" "); for (int i = 1; i <= n; i++) { a[i] = Long.valueOf(in[i - 1]); } intervalSum = calculateSum(1, (int) k); processFirstInterval(); for (int i = (int) k + 1; i <= n; i++) { // bw.write("first interval sum : " + intervalSum + "\n"); // 滑动窗口 intervalSum -= q.pollFirst()[0]; // bw.write(q.peekFirst()[0] + " "); q.offerLast(new Long[]{a[i], (long) i}); intervalSum += q.peekLast()[0]; // bw.write("interval sum : " + intervalSum + "\n"); // 处理超过sum的情况 if (intervalSum > sum) { a[i] -= intervalSum - sum; res += intervalSum - sum; q.pollLast(); q.offerLast(new Long[]{a[i], (long) i}); } } // for (int i = 1; i <= n; i++) { // bw.write(String.format("%d ", a[i])); // } bw.write(res + ""); bw.flush(); } private static long calculateSum(int st, int ed) { long res = 0L; for (int i = st; i <= ed; i++) { res += a[i]; } return res; } private static void processFirstInterval() { int tail = (int) k; if (intervalSum <= sum) { return; } while (intervalSum - sum >= a[tail]) { intervalSum -= a[tail]; res += a[tail]; a[tail--] = 0; } if (intervalSum - sum < a[tail]) { res += intervalSum - sum; a[tail] -= intervalSum - sum; intervalSum = sum; } for (int i = 1; i <= k; i++) { q.offerLast(new Long[]{a[i], (long) i}); } } }
我自测样例:
5 4 10
9 7 3 6 5
答案难道不是15?我想破脑袋也想不出来15以外的答案。
#牛客解忧铺#