java 洛谷題單【算法2-2】常見優化技巧

P1102 A-B 數對

解題思路

輸入讀取與初始化：

使用?Scanner?讀取輸入。
n?表示數組的長度，c?表示目標差值。
使用一個?HashMap?存儲數組中每個數字及其出現的次數，方便快速查找。
數組?a?用于存儲輸入的數字。

構建哈希映射：

遍歷數組，將每個數字存入?HashMap?中，鍵為數字，值為該數字出現的次數。
使用?map.getOrDefault(a[i], 0)?方法，確保即使鍵不存在也能返回默認值?0。

查找滿足條件的數對：

遍歷數組中的每個數字?a[i]，檢查是否存在?a[i] + c。
如果存在?a[i] + c，則將其出現次數累加到結果?ans?中。

輸出結果：

最終輸出符合條件的數對數量?ans。

import java.util.HashMap;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();  // 數組長度int c = input.nextInt();  // 目標差值HashMap<Integer, Integer> map = new HashMap<>();  // 用于存儲數字及其出現次數int[] a = new int[n];  // 存儲輸入的數組// 讀取數組輸入for (int i = 0; i < n; i++) {a[i] = input.nextInt();// 將數字存儲在哈希映射中map.put(a[i], map.getOrDefault(a[i], 0) + 1);}long ans = 0;  // 用于記錄符合條件的對數// 遍歷數組，尋找每個 a[i] 對應的 a[i] + c 或 a[i] - c 是否存在for (int i = 0; i < n; i++) {// 檢查是否存在 a[i] + cif (map.containsKey(a[i] + c)) {ans += map.get(a[i] + c);  // 統計滿足條件的對數}}// 輸出符合條件的對數System.out.println(ans);}
}

P1638 逛畫展

解題思路

滑動窗口：

使用兩個指針?left?和?right?表示當前窗口的左右邊界。
通過移動?right?擴大窗口，直到窗口內包含所有的名師編號。
然后移動?left?縮小窗口，嘗試找到更短的區間。

哈希表統計：

使用一個哈希表?count?記錄當前窗口內每個名師編號的出現次數。
使用一個變量?uniqueCount?記錄當前窗口內包含的不同名師編號的數量。

判斷條件：

當?uniqueCount == m?時，說明當前窗口已經包含了所有的名師編號。
記錄當前窗口的長度，并嘗試更新最優解。

輸出結果：

輸出最短區間的起始位置和結束位置?[a, b]，注意題目要求輸出的是 1-based 索引。

import java.util.*;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt(); int m = input.nextInt();int[] paintings = new int[n];for (int i = 0; i < n; i++) {paintings[i] = input.nextInt();}// 滑動窗口 + 哈希表Map<Integer, Integer> count = new HashMap<>();int uniqueCount = 0; // 當前窗口內的不同名師數量int left = 0, minLength = Integer.MAX_VALUE;int start = 0, end = 0; // 最優區間的起始和結束位置for (int right = 0; right < n; right++) {// 擴大窗口int current = paintings[right];count.put(current, count.getOrDefault(current, 0) + 1);if (count.get(current) == 1) {uniqueCount++; // 新增一個名師編號}// 縮小窗口while (uniqueCount == m) {// 更新最優解if (right - left + 1 < minLength) {minLength = right - left + 1;start = left;end = right;}// 移動左指針int leftValue = paintings[left];count.put(leftValue, count.get(leftValue) - 1);if (count.get(leftValue) == 0) {uniqueCount--; // 移除一個名師編號}left++;}}System.out.println((start + 1) + " " + (end + 1));input.close();}
}

P1115 最大子段和

解題思路

Kadane算法思想?：

維護兩個變量：current（當前子段和）和max（全局最大值）。
對于每個元素，決定是將其加入當前子段還是以該元素為起點重新開始。
通過遍歷數組一次，時間復雜度為O(n)。

import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());String[] parts = br.readLine().split(" ");int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(parts[i]);}int current = a[0];int max = a[0];for (int i = 1; i < n; i++) {current = Math.max(current + a[i], a[i]); // 更新當前子段和?max = Math.max(max, current);            // 更新全局最大值}System.out.println(max);}
}

P7072 [CSP-J2020] 直播獲獎

解題思路

該問題的核心是實時計算每次新增成績后的獲獎分數線。由于成績范圍為0-600，可以利用計數排序的思想，高效維護每個分數出現的次數，并通過累加的方式快速確定當前前k大的分數。

輸入處理?：

使用?BufferedReader?讀取輸入數據，StringTokenizer?分割字符串。
讀取選手總數?n?和獲獎率?w，接著讀取所有選手的成績存入數組?scores。

?計數數組初始化?：

count?數組大小為601（索引0到600），用于記錄每個分數出現的次數。

?遍歷處理每個成績?：

更新當前分數?s?的計數。
計算當前已處理人數?p = i + 1。
根據公式計算當前計劃獲獎人數?k，并確保至少1人獲獎。
從高分到低分（600到0）累加人數，直到總和≥k，此時的分數即為分數線。

?結果輸出?：

使用?StringBuilder?高效拼接結果字符串，最后去除末尾空格并輸出。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());int n = Integer.parseInt(st.nextToken());int w = Integer.parseInt(st.nextToken());int[] scores = new int[n];st = new StringTokenizer(br.readLine());for (int i = 0; i < n; i++) {scores[i] = Integer.parseInt(st.nextToken());}int[] count = new int[601];StringBuilder sb = new StringBuilder();for (int i = 0; i < n; i++) {int s = scores[i];count[s]++;int p = i + 1;int k = Math.max(1, (p * w) / 100);int sum = 0;int line = 0;for (int j = 600; j >= 0; j--) {sum += count[j];if (sum >= k) {line = j;break;}}sb.append(line).append(' ');}System.out.println(sb.toString().trim());}
}

P2671 [NOIP 2015 普及組] 求和

解題思路

?輸入處理與分組?：

讀取輸入的格子數量、顏色種類、每個格子的數字和顏色。
根據顏色將格子分組，并在每個顏色組內進一步按位置的奇偶性分為奇數列和偶數列。

?排序處理?：

對每個顏色組內的奇數列和偶數列按位置進行排序，以便后續處理。

?計算貢獻?：

對于每個奇數列或偶數列，計算所有可能的三元組貢獻之和。通過數學公式優化，避免雙重循環，將時間復雜度從O(n2)降為O(n)。

import java.util.*;public class Main {static class Node {int pos;int num;public Node(int pos, int num) {this.pos = pos;this.num = num;}}static final int MOD = 10007;public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int m = input.nextInt();int[] number = new int[n];for (int i = 0; i < n; i++) {number[i] = input.nextInt();}int[] color = new int[n];for (int i = 0; i < n; i++) {color[i] = input.nextInt();}// 按顏色分組，奇偶分別存儲Map<Integer, List<Node>> colorOddMap = new HashMap<>();Map<Integer, List<Node>> colorEvenMap = new HashMap<>();for (int i = 0; i < n; i++) {int c = color[i];int pos = i + 1;int num = number[i];Node node = new Node(pos, num);if (pos % 2 == 1) {colorOddMap.computeIfAbsent(c, k -> new ArrayList<>()).add(node);} else {colorEvenMap.computeIfAbsent(c, k -> new ArrayList<>()).add(node);}}// 對每個顏色的奇偶列表排序for (List<Node> list : colorOddMap.values()) {list.sort(Comparator.comparingInt(a -> a.pos));}for (List<Node> list : colorEvenMap.values()) {list.sort(Comparator.comparingInt(a -> a.pos));}long total = 0;// 處理奇列表for (List<Node> list : colorOddMap.values()) {total = (total + processList(list)) % MOD;}// 處理偶列表for (List<Node> list : colorEvenMap.values()) {total = (total + processList(list)) % MOD;}System.out.println(total % MOD);input.close();}private static long processList(List<Node> list) {int size = list.size();if (size < 2) {return 0;}// 計算sum1 = sum(pos * num)long sum1 = 0;for (Node node : list) {sum1 += (long) node.pos * node.num;}sum1 %= MOD;// sum_total = (size-1) * sum1 mod MODlong sumTotal = ((size - 1) % MOD) * sum1 % MOD;// 計算后綴和long[] sumNum = new long[size + 1];long[] sumPos = new long[size + 1];for (int i = size - 1; i >= 0; i--) {sumNum[i] = sumNum[i + 1] + list.get(i).num;sumPos[i] = sumPos[i + 1] + list.get(i).pos;}// 計算sum2long sum2 = 0;for (int i = 0; i < size; i++) {Node node = list.get(i);int currentPos = node.pos;int currentNum = node.num;long term1 = (currentPos * sumNum[i + 1]) % MOD;long term2 = (currentNum * sumPos[i + 1]) % MOD;sum2 = (sum2 + term1 + term2) % MOD;}return (sumTotal + sum2) % MOD;}
}

P4147 玉蟾宮

解題思路

該問題需要在給定的網格中找到最大的全'F'矩形面積。核心思路是逐行構建高度數組，然后利用單調棧高效計算每行對應的直方圖最大面積。具體步驟如下：

?輸入處理?：

讀取網格的行數?n?和列數?m。
逐行讀取網格數據，存儲為字符矩陣?grid。

?動態維護高度數組?：

對每一行，更新高度數組?heights。若當前格子是'F'，則高度遞增；否則重置為0。

?單調棧求最大矩形面積?：

對每一行的高度數組，使用單調棧算法計算最大矩形面積。

import java.util.*;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int m = input.nextInt();input.nextLine(); // 跳過n和m后的換行符char[][] grid = new char[n][m];for (int i = 0; i < n; i++) {String line = input.nextLine();// 分割所有空白符，包括多個空格或制表符String[] tokens = line.split("\\s+");for (int j = 0; j < m; j++) {grid[i][j] = tokens[j].charAt(0);}}int[] heights = new int[m];int maxArea = 0;for (int i = 0; i < n; i++) {// 更新當前行的高度數組for (int j = 0; j < m; j++) {if (grid[i][j] == 'F') {heights[j]++;} else {heights[j] = 0;}}// 計算當前行的最大矩形面積maxArea = Math.max(maxArea, largestRectangleArea(heights));}System.out.println(maxArea * 3);input.close();}// 單調棧計算直方圖最大矩形面積private static int largestRectangleArea(int[] heights) {Stack<Integer> stack = new Stack<>();int maxArea = 0;int n = heights.length;for (int i = 0; i <= n; i++) {// 當前高度（i=n時視為高度0以處理剩余棧元素）int currentHeight = (i == n) ? 0 : heights[i];// 維護單調遞增棧while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {int height = heights[stack.pop()];// 左邊界為棧頂元素，右邊界為當前索引iint left = stack.isEmpty() ? -1 : stack.peek();int width = i - left - 1;maxArea = Math.max(maxArea, height * width);}stack.push(i);}return maxArea;}
}

P2866 [USACO06NOV] Bad Hair Day S

解題思路

本題的目標是計算一排牛中每頭牛能看到的右邊連續較矮的牛的數量之和。核心思路是使用單調棧高效地找到每個元素右邊第一個大于等于它的位置，從而避免暴力枚舉帶來的高時間復雜度。

?棧的作用?：維護一個從棧底到棧頂單調遞增的索引序列，對應身高遞減。這保證了棧頂元素始終是當前牛右邊第一個身高不低于它的牛的位置。
?彈出條件?：當遇到當前牛的身高大于棧頂索引對應的牛的身高時，說明棧頂的牛會被當前牛擋住，后續計算無需考慮這些被擋住的牛。
?計算可見數?：若棧為空，當前牛能看到右邊所有牛；否則，可見數為棧頂索引與當前索引之間的牛的數量。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());int[] h = new int[n]; for (int i = 0; i < n; i++) {h[i] = Integer.parseInt(br.readLine());}Deque<Integer> stack = new ArrayDeque<>(); // 單調棧，存儲索引long sum = 0; // 總和可能很大，用long存儲// 從右向左遍歷每頭牛for (int i = n - 1; i >= 0; i--) {// 彈出棧中所有比當前牛矮的索引，這些牛會被當前牛擋住while (!stack.isEmpty() && h[stack.peek()] < h[i]) {stack.pop();}int c; // 當前牛能看到的牛的數量if (stack.isEmpty()) {// 棧空說明右邊所有牛都比當前牛矮c = (n - 1 - i); // 計算右邊所有牛的個數} else {// 棧頂是右邊第一個不低于當前牛的位置，中間的牛都可見c = stack.peek() - i - 1;}sum += c; // 累加到總和stack.push(i); // 將當前索引入棧}System.out.println(sum);}
}

P1950 長方形

解題思路

該問題的核心是統計所有由'.'組成的矩形的數量。關鍵思路是逐行維護一個高度數組，記錄每個位置向上連續的'.'數目，然后利用單調棧高效計算每行的貢獻。

?高度數組更新?：逐行遍歷，更新每個位置向上的連續'.'數目，遇到'*'則重置為0。
?單調棧計算貢獻?：
?左邊界計算?：維護遞增棧，找到左邊第一個比當前高度小的位置。
?右邊界計算?：維護遞增棧，找到右邊第一個比當前高度小的位置。
?累計貢獻?：每個位置的貢獻為高度乘以其左右邊界的跨度，累加得到每行的總和。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] nm = br.readLine().split(" ");int n = Integer.parseInt(nm[0]);int m = Integer.parseInt(nm[1]);char[][] grid = new char[n][m];for (int i = 0; i < n; i++) {String line = br.readLine().replaceAll("\\s+", "");for (int j = 0; j < m; j++) {grid[i][j] = line.charAt(j);}}int[] heights = new int[m];long total = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '.') {heights[j]++;} else {heights[j] = 0;}}total += calculateRowSum(heights);}System.out.println(total);}private static long calculateRowSum(int[] heights) {int m = heights.length;Deque<Integer> stack = new ArrayDeque<>();int[] left = new int[m];Arrays.fill(left, -1);// 計算left數組，左邊第一個比當前小的位置for (int i = 0; i < m; i++) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}if (!stack.isEmpty()) {left[i] = stack.peek();}stack.push(i);}stack.clear();int[] right = new int[m];Arrays.fill(right, m);// 計算right數組，右邊第一個比當前小的位置for (int i = m - 1; i >= 0; i--) {while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {stack.pop();}if (!stack.isEmpty()) {right[i] = stack.peek();}stack.push(i);}long sum = 0;for (int i = 0; i < m; i++) {sum += (long) heights[i] * (i - left[i]) * (right[i] - i);}return sum;}
}

P2032 掃描

解題思路

核心思路是使用單調隊列維護當前窗口中的最大值候選元素。?

單調隊列維護?：

?隊列清理?：在遍歷每個元素時，先移除隊列中不在當前窗口范圍內的索引（即小于?i - k + 1?的索引）。
?維護單調性?：從隊列尾部移除所有對應值小于當前元素的索引，確保隊列中的元素對應值單調遞減。
?索引入隊?：將當前元素的索引加入隊列尾部。

?窗口最大值查詢?：

當遍歷到第?i?個元素且?i >= k - 1?時，說明窗口已形成，此時隊列頭部的索引對應的值即為當前窗口的最大值，直接輸出。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());int n = Integer.parseInt(st.nextToken());int k = Integer.parseInt(st.nextToken());int[] nums = new int[n];int idx = 0;// 讀取數組元素，處理多行輸入情況while (idx < n) {if (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}nums[idx++] = Integer.parseInt(st.nextToken());}Deque<Integer> deque = new ArrayDeque<>();PrintWriter pw = new PrintWriter(System.out);for (int i = 0; i < n; i++) {// 移除隊首不在當前窗口中的元素while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {deque.pollFirst();}// 移除隊尾所有小于當前元素的索引while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();}deque.offerLast(i); // 將當前索引入隊// 當窗口形成時輸出隊首元素對應的值if (i >= k - 1) {pw.println(nums[deque.peekFirst()]);}}pw.flush();}
}

P2216 [HAOI2007] 理想的正方形

解題思路

核心思路是分階段滑動窗口極值計算：

1. 行方向極值預處理?

使用兩個雙端隊列（maxDeque?和?minDeque）分別維護當前窗口的最大值和最小值。
遍歷行中的每個元素，動態更新隊列，確保隊列頭部始終是窗口極值的索引。
結果存儲為?maxRow?和?minRow，其中?maxRow[i][j]?表示第?i?行從列?j?開始的橫向窗口的最大值，minRow?同理。

?2. 列方向極值計算與差值求解?

逐列提取數據?：對每列?j，從?maxRow?和?minRow?中提取該列的極值數據，生成臨時數組?colMax（縱向最大值列）和?colMin（縱向最小值列）。
縱向窗口處理?：對?colMax?和?colMin?分別進行長度為?n?的縱向滑動窗口處理，得到?maxWindow（縱向窗口最大值）和?minWindow（縱向窗口最小值）。
即時計算差值?：遍歷每個縱向窗口的結果，計算?maxWindow?和?minWindow?的差值，并更新全局最小差值?minDiff。

3. 內存與效率優化?

?避免顯式轉置?：通過逐列提取數據代替矩陣轉置，減少中間矩陣的內存占用。
?即時釋放內存?：每列處理完成后，臨時數組（如?colMax、colMin）可立即釋放，避免同時存儲大規模數據。
?單調隊列優化?：行和列的極值計算均通過單調隊列實現，確保時間復雜度為 ?O(a×b)?，適用于大規模矩陣。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());int a = Integer.parseInt(st.nextToken());int b = Integer.parseInt(st.nextToken());int n = Integer.parseInt(st.nextToken());int[][] mat = new int[a][b];for (int i = 0; i < a; i++) {st = new StringTokenizer(br.readLine());for (int j = 0; j < b; j++) {mat[i][j] = Integer.parseInt(st.nextToken());}}// 處理行方向的最大值和最小值int[][] maxRow = new int[a][b - n + 1];int[][] minRow = new int[a][b - n + 1];for (int i = 0; i < a; i++) {processRow(mat[i], maxRow[i], minRow[i], n);}int minDiff = Integer.MAX_VALUE;// 逐列處理，避免轉置for (int j = 0; j < maxRow[0].length; j++) {// 提取當前列的max和min數據int[] colMax = new int[a];int[] colMin = new int[a];for (int i = 0; i < a; i++) {colMax[i] = maxRow[i][j];colMin[i] = minRow[i][j];}// 處理當前列的滑動窗口int[] maxWindow = processWindow(colMax, n, true);int[] minWindow = processWindow(colMin, n, false);// 計算差值并更新最小值for (int i = 0; i < maxWindow.length; i++) {int diff = maxWindow[i] - minWindow[i];minDiff = Math.min(minDiff, diff);}}System.out.println(minDiff);}private static void processRow(int[] row, int[] maxRow, int[] minRow, int k) {Deque<Integer> maxDeque = new ArrayDeque<>();Deque<Integer> minDeque = new ArrayDeque<>();for (int j = 0; j < row.length; j++) {// 維護最大值隊列while (!maxDeque.isEmpty() && maxDeque.peekFirst() < j - k + 1) {maxDeque.pollFirst();}while (!maxDeque.isEmpty() && row[maxDeque.peekLast()] <= row[j]) {maxDeque.pollLast();}maxDeque.offerLast(j);// 維護最小值隊列while (!minDeque.isEmpty() && minDeque.peekFirst() < j - k + 1) {minDeque.pollFirst();}while (!minDeque.isEmpty() && row[minDeque.peekLast()] >= row[j]) {minDeque.pollLast();}minDeque.offerLast(j);if (j >= k - 1) {int idx = j - k + 1;maxRow[idx] = row[maxDeque.peekFirst()];minRow[idx] = row[minDeque.peekFirst()];}}}private static int[] processWindow(int[] data, int windowSize, boolean isMax) {Deque<Integer> deque = new ArrayDeque<>();int[] res = new int[data.length - windowSize + 1];for (int i = 0; i < data.length; i++) {while (!deque.isEmpty() && deque.peekFirst() < i - windowSize + 1) {deque.pollFirst();}if (isMax) {while (!deque.isEmpty() && data[deque.peekLast()] <= data[i]) {deque.pollLast();}} else {while (!deque.isEmpty() && data[deque.peekLast()] >= data[i]) {deque.pollLast();}}deque.offerLast(i);if (i >= windowSize - 1) {res[i - windowSize + 1] = data[deque.peekFirst()];}}return res;}
}

UVA11572 唯一的雪花 Unique Snowflakes

解題思路

該題的提交需要綁定UVa OJ的賬號。綁定流程參考：洛谷日報-注冊UVa OJ?、博客園-胖乎乎的王老師。注意：如果無法在Edge中打開UVa官網，請使用Google或者Firefox打開。

該問題要求找到最長的連續子數組，其中所有元素都是唯一的。使用滑動窗口（雙指針）和哈希表的方法來實現高效解決：

?滑動窗口：使用兩個指針left和right維護當前窗口，確保窗口內元素唯一。
?哈希表?：記錄每個元素最后一次出現的位置，以便快速判斷是否重復并調整窗口。

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));List<Integer> input = new ArrayList<>();String line;while ((line = br.readLine()) != null) {StringTokenizer st = new StringTokenizer(line);while (st.hasMoreTokens()) {input.add(Integer.parseInt(st.nextToken()));}}int ptr = 0;int T = input.get(ptr++);while (T-- > 0) {int n = input.get(ptr++);int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = input.get(ptr++);}System.out.println(maxUniqueSnowflakes(arr));}}private static int maxUniqueSnowflakes(int[] arr) {int max = 0;int left = 0;Map<Integer, Integer> lastSeen = new HashMap<>();for (int right = 0; right < arr.length; right++) {int num = arr[right];if (lastSeen.containsKey(num) && lastSeen.get(num) >= left) {left = lastSeen.get(num) + 1;}lastSeen.put(num, right);max = Math.max(max, right - left + 1);}return max;}
}

P4653 [CEOI 2017] Sure Bet

解題思路

該題需要我們在選擇燈泡時，系統隨機選擇A類或B類燈泡點亮后的最小收益盡可能大。我們可以通過貪心策略和二分查找來優化這個過程。

排序和前綴和?：首先將A類和B類燈泡按權值降序排列，計算前綴和數組sumA和sumB，分別表示前i個最大權值的A類和B類燈泡的總權值。
?預處理最大值數組?：預處理數組max_b，其中max_b[j]表示前j個B類燈泡的總權值減去j后的最大值。
?二分查找?：使用二分查找確定最大可能的最小收益。對于每個候選值x，檢查是否存在i和j使得選擇i個A類和j個B類燈泡時，兩種類型的最小收益至少為x。

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {// 讀取輸入BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());if (n == 0) {  // 處理n=0的特殊情況System.out.println("0.0000");return;}List<Double> A = new ArrayList<>();List<Double> B = new ArrayList<>();for (int i = 0; i < n; i++) {String[] parts = br.readLine().split(" ");double a = Double.parseDouble(parts[0]);double b = Double.parseDouble(parts[1]);A.add(a);B.add(b);}// 將A和B分別按降序排列，優先選擇權值大的燈泡Collections.sort(A, Collections.reverseOrder());Collections.sort(B, Collections.reverseOrder());// 計算前綴和數組：sumA[i]表示前i個A類燈泡的總權值 - i（每個燈泡成本為1）double[] sumA = new double[n + 1];// sumB同理double[] sumB = new double[n + 1];for (int i = 1; i <= n; i++) {sumA[i] = sumA[i - 1] + A.get(i - 1);sumB[i] = sumB[i - 1] + B.get(i - 1);}// 預處理maxB數組：maxB[j]表示前j個B類燈泡的總權值 - j后的最大值（前綴最大值）double[] maxB = new double[n + 1];double currentMax = Double.NEGATIVE_INFINITY;for (int j = 0; j <= n; j++) {double val = sumB[j] - j;     // 選擇j個B類燈泡的凈收益if (val > currentMax) {       // 維護前綴最大值currentMax = val;}maxB[j] = currentMax;}// 二分查找尋找最大可能的最小收益xdouble left = -1e9;   // 二分下界double right = 1e9;   // 二分上界// 進行100次二分迭代保證精度（比判斷差值更高效）for (int iter = 0; iter < 100; iter++) {double mid = (left + right) / 2;// 檢查是否存在i和j使得兩種情況的收益都至少為midif (isPossible(sumA, maxB, n, mid)) {left = mid;   // 可能達到mid，嘗試更大的值} else {right = mid;  // 無法達到mid，降低上界}}// 四舍五入到四位小數輸出（注意處理浮點精度）System.out.printf("%.4f\n", Math.round(left * 10000.0) / 10000.0);}// 判斷是否存在選擇i個A類燈泡和j個B類燈泡的方案，使得兩種情況的收益都至少為xprivate static boolean isPossible(double[] sumA, double[] maxB, int n, double x) {// 遍歷所有可能的A類燈泡選擇數量ifor (int i = 0; i <= n; i++) {// A類的凈收益：總權值 - i個燈泡成本 - x >= 0double aI = sumA[i] - i - x;if (aI < 0) continue;  // 不滿足條件，跳過// 計算允許的B類燈泡最大數量jMax = floor(aI)int jMax = (int) Math.floor(aI);jMax = Math.min(jMax, n);  // 不能超過總燈泡數jMax = Math.max(jMax, 0);   // 防止負數// 檢查是否存在j <= jMax，使得B類的凈收益 >= i + x// 利用預處理好的maxB數組快速查詢if (maxB[jMax] >= i + x) {return true;  // 存在滿足條件的組合}}return false;  // 遍歷完所有i仍不滿足條件}
}

P3143 [USACO16OPEN] Diamond Collector S

解題思路

該題需要找到兩個不重疊的展示柜，使得每個展示柜中的鉆石大小相差不超過K，并且兩個展示柜中的鉆石數量總和最大。思路如下：

排序：首先將所有鉆石的大小排序，以便后續處理。

預處理最長左窗口：對于每個右端點i，找到最左邊的j，使得窗口[j, i]中的鉆石大小差不超過K，并記錄每個右端點的窗口長度。

預處理最長右窗口：對于每個左端點i，找到最右邊的j，使得窗口[i, j]中的鉆石大小差不超過K，并記錄每個左端點的窗口長度。

預處理前綴最大值和后綴最大值：分別計算前綴最大值數組（每個位置之前的最大窗口長度）和后綴最大值數組（每個位置之后的最大窗口長度）。

計算最大總和：遍歷所有可能的分割點，計算左邊和右邊窗口的最大長度之和，找出最大值。

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());int n = Integer.parseInt(st.nextToken());int k = Integer.parseInt(st.nextToken());if (n < 2) {System.out.println(0);return;}int[] s = new int[n];for (int i = 0; i < n; i++) {s[i] = Integer.parseInt(br.readLine());}Arrays.sort(s);// 預處理max_left_len數組int[] maxLeftLen = new int[n];int j = 0;for (int i = 0; i < n; i++) {while (s[i] - s[j] > k) {j++;}maxLeftLen[i] = i - j + 1;}// 預處理max_right_len數組int[] maxRightLen = new int[n];j = n - 1;for (int i = n - 1; i >= 0; i--) {while (j > i && s[j] - s[i] > k) {j--;}maxRightLen[i] = j - i + 1;}// 計算前綴最大值數組leftMaxint[] leftMax = new int[n];leftMax[0] = maxLeftLen[0];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], maxLeftLen[i]);}// 計算后綴最大值數組rightMaxint[] rightMax = new int[n];rightMax[n - 1] = maxRightLen[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(maxRightLen[i], rightMax[i + 1]);}int ans = 0;for (int i = 0; i < n - 1; i++) {ans = Math.max(ans, leftMax[i] + rightMax[i + 1]);}System.out.println(ans);}
}

P7910 [CSP-J 2021] 插入排序

解題思路

?Pair類?：存儲元素的值和原下標，并實現Comparable接口，按值升序、原下標升序排序。
?初始化?：讀取輸入數據，初始化原始數組a和排序后的列表sorted。
?修改操作?：
遍歷sorted列表找到舊元素的位置并刪除。
插入新元素到正確位置，保持列表有序。

?查詢操作?：
使用二分查找計算比目標值小的元素數量。
在等于目標值的元素區間內，查找原下標小于目標位置的元素數量。

?二分查找輔助函數?：實現bisectLeft、bisectRight和bisectIndex，用于快速定位插入點和統計元素數量。

import java.util.*;
import java.io.*;// 自定義Pair類，存儲元素值和原下標，并實現Comparable接口以便排序
class Pair implements Comparable<Pair> {int value;int index;public Pair(int value, int index) {this.value = value;this.index = index;}@Overridepublic int compareTo(Pair o) {if (this.value != o.value) {return Integer.compare(this.value, o.value);} else {return Integer.compare(this.index, o.index);}}
}public class Main {// 原始數組，存儲當前每個元素的值static int[] a;// 排序后的列表，按值升序、原下標升序排列static List<Pair> sorted = new ArrayList<>();public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter out = new PrintWriter(System.out);String[] firstLine = br.readLine().split(" ");int n = Integer.parseInt(firstLine[0]);int Q = Integer.parseInt(firstLine[1]);a = new int[n + 1]; // 原下標從1開始String[] aValues = br.readLine().split(" ");for (int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aValues[i - 1]);}// 初始化sorted列表for (int i = 1; i <= n; i++) {sorted.add(new Pair(a[i], i));}Collections.sort(sorted);for (int q = 0; q < Q; q++) {String[] op = br.readLine().split(" ");if (op[0].equals("1")) { // 修改操作int x = Integer.parseInt(op[1]);int v = Integer.parseInt(op[2]);modify(x, v);} else { // 查詢操作int x = Integer.parseInt(op[1]);int ans = query(x);out.println(ans);}}out.flush();}// 處理修改操作，將原下標x的元素值更新為vprivate static void modify(int x, int v) {// 找到舊元素在sorted中的位置int oldIndex = -1;for (int i = 0; i < sorted.size(); i++) {if (sorted.get(i).index == x) {oldIndex = i;break;}}// 刪除舊元素sorted.remove(oldIndex);// 插入新元素到正確位置Pair newPair = new Pair(v, x);int insertPos = bisectLeft(sorted, newPair);sorted.add(insertPos, newPair);// 更新原數組a[x] = v;}// 處理查詢操作，返回原下標x的元素在排序后的位置private static int query(int x) {int v = a[x];// 計算比v小的元素數量Pair keyStart = new Pair(v, Integer.MIN_VALUE);int start = bisectLeft(sorted, keyStart);int lessCount = start;// 計算等于v且原下標小于x的元素數量int equalLessCount = 0;if (start < sorted.size() && sorted.get(start).value == v) {// 找到等于v的區間[start, end)Pair keyEnd = new Pair(v, Integer.MAX_VALUE);int end = bisectRight(sorted, keyEnd);// 在[start, end)區間內查找原下標小于x的元素數量equalLessCount = bisectIndex(start, end, x) - start;}return lessCount + equalLessCount + 1;}// 在sorted列表的[start, end)區間內，找到第一個原下標>=x的位置private static int bisectIndex(int start, int end, int targetIndex) {int low = start;int high = end;while (low < high) {int mid = (low + high) / 2;int midIndex = sorted.get(mid).index;if (midIndex < targetIndex) {low = mid + 1;} else {high = mid;}}return low;}// 實現bisect_left功能，找到插入點private static int bisectLeft(List<Pair> list, Pair key) {int low = 0;int high = list.size();while (low < high) {int mid = (low + high) / 2;Pair midVal = list.get(mid);if (midVal.compareTo(key) < 0) {low = mid + 1;} else {high = mid;}}return low;}// 實現bisect_right功能，找到插入點private static int bisectRight(List<Pair> list, Pair key) {int low = 0;int high = list.size();while (low < high) {int mid = (low + high) / 2;Pair midVal = list.get(mid);if (midVal.compareTo(key) <= 0) {low = mid + 1;} else {high = mid;}}return low;}
}

P1578 奶牛浴場

解題思路

該題實際上是需要我們在給定的二維區域（邊界為?[0, N] × [0, M]）和?K?個障礙點的情況下，找到最大的無障礙矩形區域。

?1. 添加邊界點?

在輸入的?K?個障礙點基礎上，添加四個角落的邊界點：(N,0),?(N,M),?(0,M),?(0,0)。
?目的?：確保最大矩形可能緊貼區域邊界的情況被覆蓋。

2. 按 X 軸排序后處理橫向擴展?

?排序?：將所有點按?x?坐標升序排列（x?相同則按?y?排序）。
?遍歷每個點?：對每個點?a[i]，向右和向左兩個方向尋找可能的矩形：
?向右擴展?（j = i+1?開始）：
維護上下邊界?h1（上邊界）和?h2（下邊界）。
若遇到障礙點，調整上下邊界以縮小可能的矩形高度。
計算當前橫向長度?v = a[j].x - a[i].x，并更新最大面積。

?向左擴展?（j = i-1?開始）：
類似向右擴展，但橫向長度為?v = a[i].x - a[j].x。

?剪枝優化?：若當前可能的面積已小于已記錄的最大值，則提前跳出循環。

?3. 按 Y 軸排序后處理垂直擴展?

?排序?：將所有點按?y?坐標升序排列。
?遍歷相鄰點?：計算相鄰兩點?a[i]?和?a[i+1]?之間的垂直距離?(a[i+1].y - a[i].y)。
?最大垂直矩形?：由于水平方向無約束，寬度為?N，面積為?N * (a[i+1].y - a[i].y)。

import java.util.Arrays;
import java.util.Scanner;// 定義一個節點類，用于存儲坐標信息
class Node {int x, y;// 構造函數，用于初始化節點的 x 和 y 坐標Node(int x, int y) {this.x = x;this.y = y;}
}public class Main {// 用于數組的最大長度static final int MAX = 5000 + 7;// 用于存儲所有的節點信息static Node[] a = new Node[MAX];// N 和 M 可能表示區域的邊界，K 表示節點數量，ans 用于存儲最終結果static int N, M, K, ans;public static void main(String[] args) {Scanner input = new Scanner(System.in);N = input.nextInt();M = input.nextInt();K = input.nextInt();for (int i = 1; i <= K; i++) {int x = input.nextInt();int y = input.nextInt();a[i] = new Node(x, y);}a[++K] = new Node(N, 0);a[++K] = new Node(N, M);a[++K] = new Node(0, M);a[++K] = new Node(0, 0);// 按照 x 坐標升序排序，如果 x 坐標相同，則按照 y 坐標升序排序Arrays.sort(a, 1, K + 1, (n1, n2) -> {if (n1.x != n2.x) {return n1.x - n2.x;}return n1.y - n2.y;});for (int i = 1; i <= K; i++) {// 初始化 h1 為 M，h2 為 0，v 為 N - a[i].x，fa 為 0// h1 和 h2 用于記錄當前的上下邊界，v 用于記錄當前的橫向長度，fa 用于標記是否遇到特殊情況int h1 = M, h2 = 0, v = N - a[i].x, fa = 0;for (int j = i + 1; j <= K; j++) {if (a[j].y <= h1 && a[i].y >= h2) {// 如果當前可能的矩形面積小于等于已記錄的最大面積，則跳出循環if (v * (h1 - h2) <= ans) {break;}// 更新最大面積ans = Math.max(ans, (h1 - h2) * (a[j].x - a[i].x));// 如果當前節點的 y 坐標等于當前節點的 y 坐標if (a[j].y == a[i].y) {// 標記為遇到特殊情況fa = 1;break;}// 如果當前節點的 y 坐標大于當前節點的 y 坐標，更新 h1 為較小值if (a[j].y > a[i].y) {h1 = Math.min(h1, a[j].y);} else {// 否則更新 h2 為較大值h2 = Math.max(h2, a[j].y);}}}// 如果沒有遇到特殊情況，更新最大面積if (fa == 0) {ans = Math.max(ans, v * (h1 - h2));}// 重新初始化 h1、h2、v 和 fah1 = M;h2 = 0;v = a[i].x;fa = 0;// 從當前節點的前一個節點開始向前遍歷for (int j = i - 1; j >= 1; j--) {// 如果當前節點的 y 坐標在 h1 和 h2 之間if (a[j].y <= h1 && a[i].y >= h2) {// 如果當前可能的矩形面積小于等于已記錄的最大面積，則跳出循環if (v * (h1 - h2) <= ans) {break;}// 更新最大面積ans = Math.max(ans, (h1 - h2) * (a[i].x - a[j].x));// 如果當前節點的 y 坐標等于當前節點的 y 坐標if (a[j].y == a[i].y) {// 標記為遇到特殊情況fa = 1;break;}// 如果當前節點的 y 坐標大于當前節點的 y 坐標，更新 h1 為較小值if (a[j].y > a[i].y) {h1 = Math.min(h1, a[j].y);} else {// 否則更新 h2 為較大值h2 = Math.max(h2, a[j].y);}}}// 如果沒有遇到特殊情況，更新最大面積if (fa == 0) {ans = Math.max(ans, v * (h1 - h2));}}// 按照 y 坐標升序排序Arrays.sort(a, 1, K + 1, (n1, n2) -> n1.y - n2.y);// 遍歷所有節點，更新最大面積for (int i = 1; i < K; i++) {ans = Math.max(ans, (a[i + 1].y - a[i].y) * N);}System.out.println(ans);input.close();}
}

P3467 [POI 2008] PLA-Postering

解題思路

這個問題需要我們找到最少數量的矩形海報，以覆蓋所有建筑的北立面。每個海報必須覆蓋連續的區間，并且其高度必須至少是該區間內所有建筑的最大高度。可以使用單調棧來解決這個問題。

排序和單調棧：我們使用單調遞增棧來維護當前處理的高度序列。每次遇到一個新的高度時，彈出所有比當前高度大的棧頂元素，并記錄彈出的次數。

合并相同高度：如果當前高度與棧頂高度相同，則可以合并到同一個海報中，無需增加計數。

統計結果：最終的結果為彈出的次數加上棧中剩余的元素數目，這表示所有需要分開的區域數量。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());int[] heights = new int[n];for (int i = 0; i < n; i++) {StringTokenizer st = new StringTokenizer(br.readLine());st.nextToken(); // 寬度不需要，只取高度heights[i] = Integer.parseInt(st.nextToken());}Deque<Integer> stack = new ArrayDeque<>();int count = 0;for (int h : heights) {while (!stack.isEmpty() && stack.peek() > h) {stack.pop();count++;}if (stack.isEmpty() || stack.peek() < h) {stack.push(h);}}System.out.println(count + stack.size());}
}

P1886 滑動窗口 /【模板】單調隊列

解題思路

解決滑動窗口中的最大值和最小值問題，我們可以使用單調隊列來高效地維護窗口內的元素。

單調隊列維護最小值?：使用一個單調遞增隊列來維護窗口內的最小值。隊列中保存元素的索引，保證隊列中的元素值嚴格遞增。當新元素進入窗口時，移除隊列中所有比它大的元素，因為這些元素不可能成為后續窗口的最小值。
?單調隊列維護最大值?：使用一個單調遞減隊列來維護窗口內的最大值。隊列中保存元素的索引，保證隊列中的元素值嚴格遞減。當新元素進入窗口時，移除隊列中所有比它小的元素，因為這些元素不可能成為后續窗口的最大值。
?窗口范圍檢查?：每次處理新元素時，檢查隊列頭部元素是否超出當前窗口范圍，若超出則移除，確保隊列中的元素始終在當前窗口內。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));StringTokenizer st = new StringTokenizer(br.readLine());int n = Integer.parseInt(st.nextToken());int k = Integer.parseInt(st.nextToken());int[] a = new int[n];st = new StringTokenizer(br.readLine());for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(st.nextToken());}// 處理最小值Deque<Integer> minDeque = new ArrayDeque<>();List<Integer> minResult = new ArrayList<>();for (int i = 0; i < n; i++) {// 移除超出窗口的元素while (!minDeque.isEmpty() && minDeque.peekFirst() < i - k + 1) {minDeque.pollFirst();}// 移除比當前元素大的元素while (!minDeque.isEmpty() && a[i] <= a[minDeque.peekLast()]) {minDeque.pollLast();}minDeque.offerLast(i);if (i >= k - 1) {minResult.add(a[minDeque.peekFirst()]);}}// 處理最大值Deque<Integer> maxDeque = new ArrayDeque<>();List<Integer> maxResult = new ArrayList<>();for (int i = 0; i < n; i++) {// 移除超出窗口的元素while (!maxDeque.isEmpty() && maxDeque.peekFirst() < i - k + 1) {maxDeque.pollFirst();}// 移除比當前元素小的元素while (!maxDeque.isEmpty() && a[i] >= a[maxDeque.peekLast()]) {maxDeque.pollLast();}maxDeque.offerLast(i);if (i >= k - 1) {maxResult.add(a[maxDeque.peekFirst()]);}}// 輸出結果StringBuilder sb = new StringBuilder();for (int num : minResult) {sb.append(num).append(' ');}sb.setLength(sb.length() - 1);sb.append('\n');for (int num : maxResult) {sb.append(num).append(' ');}sb.setLength(sb.length() - 1);bw.write(sb.toString());bw.flush();}
}

P2880 [USACO07JAN] Balanced Lineup G

解題思路

該題需要解決多次查詢區間內最大值和最小值的差值問題。采用稀疏表（ST表）數據結構。

?輸入處理：?? 讀取牛的數量n和查詢次數q，隨后讀取每頭牛的身高存入數組h。
?預處理ST表：??
構建兩個二維數組st_max和st_min，分別存儲區間最大值和最小值。
初始層（j=0）每個區間的長度為1，最大值和最小值即為該位置的元素。
對于每一層j，將區間分為兩半，分別取前半段和后半段的最值，合并后得到當前層的最值。

?處理查詢：??
對于每個查詢區間[a, b]，轉換為0-based的索引[L, R]。
計算區間長度對應的冪次k，將區間分為兩個重疊的2^k長度的區間，分別查詢最值后取結果。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter out = new PrintWriter(System.out);StringTokenizer st = new StringTokenizer(br.readLine());int n = Integer.parseInt(st.nextToken());int q = Integer.parseInt(st.nextToken());int[] h = new int[n];for (int i = 0; i < n; i++) {h[i] = Integer.parseInt(br.readLine());}// 預處理ST表int log_max = 0;while ((1 << (log_max + 1)) <= n) {log_max++;}int[][] st_max = new int[log_max + 1][n];int[][] st_min = new int[log_max + 1][n];for (int i = 0; i < n; i++) {st_max[0][i] = h[i];st_min[0][i] = h[i];}for (int j = 1; j <= log_max; j++) {for (int i = 0; i + (1 << j) <= n; i++) {int prev = 1 << (j - 1);st_max[j][i] = Math.max(st_max[j - 1][i], st_max[j - 1][i + prev]);st_min[j][i] = Math.min(st_min[j - 1][i], st_min[j - 1][i + prev]);}}// 處理查詢for (int i = 0; i < q; i++) {st = new StringTokenizer(br.readLine());int a = Integer.parseInt(st.nextToken());int b = Integer.parseInt(st.nextToken());int L = a - 1;int R = b - 1;int len = R - L + 1;int k = 31 - Integer.numberOfLeadingZeros(len);int max_val = Math.max(st_max[k][L], st_max[k][R - (1 << k) + 1]);int min_val = Math.min(st_min[k][L], st_min[k][R - (1 << k) + 1]);out.println(max_val - min_val);}out.flush();}
}

P1714 切蛋糕

解題思路

這題需要找到給定數組中長度不超過 m 的連續子數組，使得它們的和最大。可以通過使用前綴和和單調隊列解決。

前綴和數組：計算前綴和數組，以便快速計算任意子數組的和。

單調隊列維護：使用單調隊列來維護當前窗口內的最小前綴和值，從而快速找到每個右端點對應的最大子數組和。

滑動窗口處理：遍歷每個右端點，維護隊列中的元素在有效窗口范圍內，并更新最大值。

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] line = br.readLine().split(" ");int n = Integer.parseInt(line[0]);int m = Integer.parseInt(line[1]);int[] p = new int[n];String[] nums = br.readLine().split(" ");for (int i = 0; i < n; i++) {p[i] = Integer.parseInt(nums[i]);}long[] s = new long[n + 1];for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + p[i - 1];}Deque<Integer> deque = new ArrayDeque<>();deque.addLast(0);long max = s[1] - s[0];  // 初始化為第一個元素的值for (int r = 1; r <= n; r++) {// 移除超出窗口的左端點while (!deque.isEmpty() && deque.peekFirst() < r - m) {deque.pollFirst();}// 計算當前最大值if (!deque.isEmpty()) {long current = s[r] - s[deque.peekFirst()];if (current > max) {max = current;}}// 維護單調遞增隊列while (!deque.isEmpty() && s[r] <= s[deque.peekLast()]) {deque.pollLast();}deque.addLast(r);}System.out.println(max);}
}

P1725 琪露諾

解題思路

該題需要找到最大冰凍指數，考慮到每個位置的決策依賴之前的位置狀態以及滑動窗口的最大值，使用dp+單調隊列。

?輸入處理?：讀取輸入的N、L、R和冰凍指數數組A。數組A的大小為N+1，對應編號0到N的格子。

?初始化動態規劃數組?：dp[i]表示到達第i個格子時的最大冰凍指數。初始時，只有dp[0] = 0（起始位置），其余設為最小值。

?單調隊列維護?：使用雙端隊列維護當前可到達的候選位置，確保隊列中的元素（位置索引）對應的dp值單調遞減，從而快速獲取區間最大值。

?狀態轉移?：對于每個位置i，通過隊列找到可跳轉到i的候選位置中的最大值，更新dp[i]。隊列維護窗口范圍為[i-R, i-L]，確保時間復雜度為O(N)。

?結果計算?：遍歷所有可能直接跳到對岸的位置（即滿足i + R >= N+1的位置），取最大的dp值作為最終結果。

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());int N = Integer.parseInt(st.nextToken());int L = Integer.parseInt(st.nextToken());int R = Integer.parseInt(st.nextToken());int[] A = new int[N + 1];st = new StringTokenizer(br.readLine());for (int i = 0; i <= N; i++) {A[i] = Integer.parseInt(st.nextToken());}int[] dp = new int[N + 1];Arrays.fill(dp, Integer.MIN_VALUE);dp[0] = 0; // 初始位置在0號格子，冰凍指數為0Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i <= N; i++) {// 將可以跳到當前i的候選j（即j_end = i - L）加入隊列if (i >= L) {int jEnd = i - L;// 維護隊列單調遞減，確保隊列末尾的元素的dp值 >= 當前jEnd的dp值while (!deque.isEmpty() && dp[jEnd] >= dp[deque.peekLast()]) {deque.pollLast();}deque.addLast(jEnd);}// 移除隊列中不在當前窗口[i-R, i-L]范圍內的元素int windowLeft = i - R;while (!deque.isEmpty() && deque.peekFirst() < windowLeft) {deque.pollFirst();}// 計算dp[i]if (i == 0) {continue; // dp[0]已經初始化}if (i >= L) {if (!deque.isEmpty()) {dp[i] = dp[deque.peekFirst()] + A[i];} // 否則保持為MIN_VALUE} // 否則保持為MIN_VALUE}// 尋找最終的最大值：所有滿足i + R >= N+1的dp[i]int result = Integer.MIN_VALUE;int lower = Math.max(0, (N + 1) - R);for (int i = lower; i <= N; i++) {if (dp[i] > result) {result = dp[i];}}System.out.println(result);}
}