java 洛谷題單【算法2-1】前綴和、差分與離散化

P8218 【深進1.例1】求區間和

解題思路

前綴和數組：

prefixSum[i]?表示數組?a?的前 (i) 項的和。
通過?prefixSum[r] - prefixSum[l - 1]?可以快速計算區間 ([l, r]) 的和。

時間復雜度：

構建前綴和數組的時間復雜度是 (O(n))。
每次查詢的時間復雜度是 (O(1))。
總體時間復雜度從原來的 (O(m \cdot n)) 降低到 (O(n + m))。

空間復雜度：

額外使用了一個長度為 (n + 1) 的前綴和數組，空間復雜度是 (O(n))。

這里首先使用常規思路解題，思路沒錯，但是會超時，使用前綴后之后，用空間換時間避免超時。?

常規思路?

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int[] a = new int[n];for (int i = 0; i < a.length; i++) {a[i] = input.nextInt();}int m = input.nextInt();int ans = 0;while (m-- > 0) {int l = input.nextInt();int r = input.nextInt();for (int i = l; i <= r; i++) {ans += a[i - 1];}System.out.println(ans);ans = 0;}input.close();}
}

前綴和（AC代碼）

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int[] a = new int[n];int[] prefixSum = new int[n + 1]; // 前綴和數組，prefixSum[0] = 0// 讀取數組并計算前綴和for (int i = 0; i < n; i++) {a[i] = input.nextInt();prefixSum[i + 1] = prefixSum[i] + a[i];}int m = input.nextInt();while (m-- > 0) {int l = input.nextInt();int r = input.nextInt();// 使用前綴和計算區間和int ans = prefixSum[r] - prefixSum[l - 1];System.out.println(ans);}input.close();}
}

P1719 最大加權矩形

解題思路

枚舉上下邊界：

使用兩個嵌套循環?top?和?bottom，分別表示矩形的上邊界和下邊界。
在固定上下邊界后，將矩陣壓縮為一維數組?temp，其中?temp[col]?表示當前上下邊界內第?col?列的累加和。

Kadane 算法：

對壓縮后的一維數組?temp?使用 Kadane 算法，快速計算最大子數組和。
Kadane 算法的時間復雜度是 (O(n))。

更新最大值：

每次計算出當前上下邊界內的最大子數組和后，更新全局最大值?maxSum。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int[][] a = new int[n][n];for (int i = 0; i < a.length; i++) {for (int j = 0; j < a.length; j++) {a[i][j] = input.nextInt();}}int maxSum = Integer.MIN_VALUE;// 枚舉上下邊界for (int top = 0; top < n; top++) {int[] temp = new int[n]; // 用于存儲列的累加和for (int bottom = top; bottom < n; bottom++) {// 計算當前上下邊界內每列的累加和for (int col = 0; col < n; col++) {temp[col] += a[bottom][col];}// 使用 Kadane 算法計算一維數組的最大子數組和maxSum = Math.max(maxSum, maxSubArraySum(temp));}}System.out.println(maxSum);input.close();}// 一維最大子數組和（Kadane 算法）private static int maxSubArraySum(int[] arr) {int maxSum = arr[0];int currentSum = arr[0];for (int i = 1; i < arr.length; i++) {currentSum = Math.max(arr[i], currentSum + arr[i]);maxSum = Math.max(maxSum, currentSum);}return maxSum;}
}

P1314 [NOIP 2011 提高組] 聰明的質監員

解題思路

輸入處理：

使用?BufferedReader?和?StringTokenizer?讀取輸入。
礦石的重量和價值存儲在數組?w?和?v?中。
區間的左右端點存儲在數組?l?和?r?中。

二分查找：

使用變量?ans?表示當前的候選參數 $W$ 。
從高位到低位逐步嘗試增加 $W$ 的值，直到找到滿足條件的最大 $W$。

輔助函數?Y：

計算當前參數 $W$ 對應的檢驗值 $y$ 。
使用前綴和數組?s1?和?s2?快速計算區間內的權重和價值總和。

結果計算：

比較 $Y(ans)$ 和 $Y(ans + 1)$ ，取與 $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));StringTokenizer st = new StringTokenizer(br.readLine());// 讀取礦石數量 n、區間數量 m 和目標值 sint n = Integer.parseInt(st.nextToken());int m = Integer.parseInt(st.nextToken());long s = Long.parseLong(st.nextToken());// 讀取每個礦石的重量 w 和價值 vint[] w = new int[n + 1];int[] v = new int[n + 1];for (int i = 1; i <= n; i++) {st = new StringTokenizer(br.readLine());w[i] = Integer.parseInt(st.nextToken());v[i] = Integer.parseInt(st.nextToken());}// 讀取每個區間的左右端點int[][] intervals = new int[m][2];for (int i = 0; i < m; i++) {st = new StringTokenizer(br.readLine());intervals[i][0] = Integer.parseInt(st.nextToken());intervals[i][1] = Integer.parseInt(st.nextToken());}// 找到礦石的最大重量，用于二分查找的右邊界int max_w = 0;for (int i = 1; i <= n; i++) {if (w[i] > max_w) {max_w = w[i];}}// 初始化二分查找的左右邊界int left = 0;int right = max_w + 1;long minDiff = Long.MAX_VALUE; // 記錄最小的 |s - y|// 輔助數組，用于前綴和計算long[] cnt = new long[n + 1];    // 記錄滿足條件的礦石數量的前綴和long[] sum_v = new long[n + 1]; // 記錄滿足條件的礦石價值的前綴和// 二分查找，尋找使 |s - y| 最小的參數 Wwhile (left <= right) {int mid = (left + right) >>> 1; // 取中間值作為當前的 W// 重置前綴和數組Arrays.fill(cnt, 0);Arrays.fill(sum_v, 0);// 計算前綴和數組for (int i = 1; i <= n; i++) {if (w[i] >= mid) { // 如果當前礦石的重量滿足條件cnt[i] = cnt[i - 1] + 1; // 累加滿足條件的礦石數量sum_v[i] = sum_v[i - 1] + v[i]; // 累加滿足條件的礦石價值} else {cnt[i] = cnt[i - 1]; // 不滿足條件，數量保持不變sum_v[i] = sum_v[i - 1]; // 不滿足條件，價值保持不變}}// 計算所有區間的檢驗值 ylong total = 0;for (int i = 0; i < m; i++) {int l = intervals[i][0];int r = intervals[i][1];// 計算區間 [l, r] 內滿足條件的礦石數量和價值long count = cnt[r] - cnt[l - 1];long sum = sum_v[r] - sum_v[l - 1];total += count * sum; // 累加到總檢驗值}// 計算當前檢驗值與目標值 s 的差值long diff = Math.abs(total - s);if (diff < minDiff) { // 更新最小差值minDiff = diff;}// 根據當前檢驗值調整二分查找的范圍if (total > s) {left = mid + 1; // 檢驗值過大，增大 W} else {right = mid - 1; // 檢驗值過小，減小 W}}// 輸出最小的 |s - y|System.out.println(minDiff);}
}

P2367 語文成績

解題思路

?差分數組?：差分數組允許我們在O(1)時間內完成區間加減操作。差分數組d的第i個元素表示原數組a中第i個元素與前一個元素的差值。
?區間操作處理?：對于每個區間操作(x, y, z)，我們只需在差分數組的d[x]加上z，并在d[y+1]減去z。
?前綴和計算?：通過計算差分數組的前綴和，我們可以得到每個學生的最終成績，并找到其中的最小值。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer st = new StreamTokenizer(br);st.nextToken();int n = (int) st.nval;st.nextToken();int p = (int) st.nval;int[] d = new int[n + 2];// 構造差分數組st.nextToken();int aPrev = (int) st.nval;d[1] = aPrev;for (int i = 2; i <= n; i++) {st.nextToken();int aCurrent = (int) st.nval;d[i] = aCurrent - aPrev;aPrev = aCurrent;}// 處理區間操作for (int i = 0; i < p; i++) {st.nextToken();int x = (int) st.nval;st.nextToken();int y = (int) st.nval;st.nextToken();int z = (int) st.nval;d[x] += z;d[y + 1] -= z;}// 計算前綴和并找最小值int sum = 0;int min = Integer.MAX_VALUE;for (int i = 1; i <= n; i++) {sum += d[i];if (sum < min) {min = sum;}}System.out.println(min);}
}

P3397 地毯

解題思路

?二維差分數組?：差分數組是一種用于高效處理區間更新操作的數據結構。通過記錄區間的起點和終點的變化量，我們可以在最后通過前綴和每個點的最終覆蓋次數。
?差分操作?：對于每個地毯覆蓋的矩形區域，我們更新差分數組的四個角點，分別進行加1和減1操作。
?前綴和計算?：通過兩次前綴和計算（先按行，再按列），我們可以將差分數組轉換為每個點的實際覆蓋次數。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int m = input.nextInt();int[][] d = new int[n + 2][n + 2]; // 使用n+2的數組來避免越界for (int k = 0; k < m; k++) {int x1 = input.nextInt();int y1 = input.nextInt();int x2 = input.nextInt();int y2 = input.nextInt();// 應用差分數組的四個操作d[x1][y1]++;d[x1][y2 + 1]--;d[x2 + 1][y1]--;d[x2 + 1][y2 + 1]++;}// 計算行前綴和for (int i = 1; i <= n + 1; i++) {for (int j = 1; j <= n + 1; j++) {d[i][j] += d[i][j - 1];}}// 計算列前綴和for (int j = 1; j <= n + 1; j++) {for (int i = 1; i <= n + 1; i++) {d[i][j] += d[i - 1][j];}}// 輸出結果for (int i = 1; i <= n; i++) {StringBuilder sb = new StringBuilder();for (int j = 1; j <= n; j++) {sb.append(d[i][j]);if (j < n) {sb.append(" ");}}System.out.println(sb);}input.close();}
}

P1496 火燒赤壁

解題思路

輸入處理：將所有的區間存儲在?List<int[]>?中，每個區間用一個長度為 2 的數組表示。

排序：按區間的起點升序排序，如果起點相同，則按終點升序排序。

區間合并：遍歷排序后的區間列表，判斷當前區間是否與前一個區間重疊：

如果不重疊，則將前一個區間的長度累加到總長度中，并更新當前區間為新的起點和終點。
如果重疊，則更新當前區間的結束點。

輸出結果：最后將最后一個區間的長度累加到總長度中。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();// 用于存儲所有區間List<int[]> intervals = new ArrayList<>();for (int i = 0; i < n; i++) {int a = input.nextInt();int b = input.nextInt();intervals.add(new int[]{a, b});}// 按起點排序，如果起點相同按終點排序Collections.sort(intervals, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);// 合并區間并計算總長度int totalLength = 0;int start = intervals.get(0)[0];int end = intervals.get(0)[1];for (int i = 1; i < intervals.size(); i++) {int[] current = intervals.get(i);if (current[0] <= end) {// 當前區間與前一個區間重疊或相連，更新結束點end = Math.max(end, current[1]);} else {// 當前區間與前一個區間不重疊，累加長度并更新起點和終點totalLength += end - start;start = current[0];end = current[1];}}// 累加最后一個區間的長度totalLength += end - start;System.out.println(totalLength);input.close();}
}

P1955 [NOI2015] 程序自動分析

解題思路

初始化并查集：高效處理連通性問題，每個元素初始時是獨立的集合。
處理相等約束：將相等的元素合并到同一個集合。
處理不等約束：
檢查不等的元素是否已經連通。
如果連通，則違反約束，返回?NO。

輸出結果：如果所有約束都滿足，返回?YES。

import java.util.*;public class Main {// Union-Find 數據結構，用于高效處理連通性問題static class UnionFind {private final Map<Integer, Integer> parent = new HashMap<>();// 查找操作，帶路徑壓縮優化public int find(int x) {if (!parent.containsKey(x)) { // 如果 x 不在 parent 中，初始化為自身parent.put(x, x);}if (parent.get(x) != x) { // 路徑壓縮，將 x 的父節點直接指向根節點parent.put(x, find(parent.get(x)));}return parent.get(x);}// 合并操作，將兩個集合合并public void union(int x, int y) {int rootX = find(x); // 找到 x 的根節點int rootY = find(y); // 找到 y 的根節點if (rootX != rootY) { // 如果根節點不同，合并兩個集合parent.put(rootY, rootX);}}// 判斷兩個元素是否在同一個集合中public boolean connected(int x, int y) {return find(x) == find(y);}}// 處理單個測試用例，判斷約束是否滿足public static String solveCase(List<int[]> constraints) {UnionFind uf = new UnionFind(); List<int[]> notEqualPairs = new ArrayList<>(); // 存儲不等約束的對// 遍歷所有約束for (int[] constraint : constraints) {int x = constraint[0]; int y = constraint[1]; int e = constraint[2]; // 約束類型 (1 表示相等，0 表示不等)if (e == 1) {uf.union(x, y); // 如果是相等約束，合并兩個元素} else {notEqualPairs.add(new int[] { x, y }); // 如果是不等約束，加入列表}}// 檢查所有不等約束是否被違反for (int[] pair : notEqualPairs) {if (uf.connected(pair[0], pair[1])) { // 如果兩個元素已經連通，則違反約束return "NO"; }}return "YES"; }public static void main(String[] args) {Scanner input = new Scanner(System.in); int t = input.nextInt(); StringBuilder result = new StringBuilder(); // 用于存儲所有測試用例的結果// 遍歷每個測試用例for (int i = 0; i < t; i++) {int n = input.nextInt(); // 讀取當前測試用例的約束數量List<int[]> constraints = new ArrayList<>(); // 存儲當前測試用例的約束for (int j = 0; j < n; j++) {int x = input.nextInt(); int y = input.nextInt(); int e = input.nextInt(); // 讀取約束類型 (1 表示相等，0 表示不等)constraints.add(new int[] { x, y, e }); // 將約束加入列表}String res = solveCase(constraints); // 處理當前測試用例result.append(res).append("\n"); }System.out.print(result); input.close();}
}

P1884 [USACO12FEB] Overplanting S

解題思路

離散化坐標：

由于坐標范圍很大（-10^8?到?10^8），直接操作會導致內存和時間復雜度過高。
我們可以將所有矩形的橫坐標和縱坐標進行離散化，映射到一個較小的索引范圍。

掃描線算法：

按照矩形的橫坐標（x?值）排序，依次處理每個矩形的左邊界和右邊界。
使用一個差分數組或線段樹來維護當前被覆蓋的縱坐標區間。

計算面積：

每次掃描到一個新的橫坐標時，根據當前的覆蓋區間計算面積增量。
面積增量等于當前覆蓋的縱坐標長度乘以橫坐標的變化量。

import java.util.*;public class Main {static class Event implements Comparable<Event> {int x, y1, y2, type; // x坐標，y區間，type=1表示矩形左邊界，type=-1表示右邊界public Event(int x, int y1, int y2, int type) {this.x = x;this.y1 = y1;this.y2 = y2;this.type = type;}@Overridepublic int compareTo(Event other) {return this.x - other.x; // 按x坐標排序}}public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();List<Event> events = new ArrayList<>();Set<Integer> yCoords = new HashSet<>();// 讀取矩形信息for (int i = 0; i < n; i++) {int x1 = input.nextInt();int y1 = input.nextInt();int x2 = input.nextInt();int y2 = input.nextInt();// 確保y1 < y2if (y1 > y2) {int temp = y1;y1 = y2;y2 = temp;}// 添加事件events.add(new Event(x1, y1, y2, 1));  // 左邊界events.add(new Event(x2, y1, y2, -1)); // 右邊界// 收集所有y坐標yCoords.add(y1);yCoords.add(y2);}// 離散化y坐標List<Integer> sortedY = new ArrayList<>(yCoords);Collections.sort(sortedY);Map<Integer, Integer> yIndex = new HashMap<>();for (int i = 0; i < sortedY.size(); i++) {yIndex.put(sortedY.get(i), i);}// 按x坐標排序事件Collections.sort(events);// 差分數組，記錄每個離散化y區間的覆蓋次數int[] count = new int[sortedY.size()];long totalArea = 0;int prevX = events.get(0).x;// 掃描線處理for (Event event : events) {int currX = event.x;// 計算當前覆蓋的y區間長度long coveredLength = 0;for (int i = 0; i < count.length - 1; i++) {if (count[i] > 0) {coveredLength += sortedY.get(i + 1) - sortedY.get(i);}}// 累加面積totalArea += coveredLength * (currX - prevX);// 更新差分數組int y1Index = yIndex.get(event.y1);int y2Index = yIndex.get(event.y2);for (int i = y1Index; i < y2Index; i++) {count[i] += event.type;}// 更新prevXprevX = currX;}// 輸出結果System.out.println(totalArea);input.close();}
}

P2004 領地選擇

解題思路

第七個測試點如果MLE，多試幾次就能過。

二維前綴和：

構建一個二維前綴和數組?prefix，其中?prefix[i][j]?表示從地圖左上角?(1, 1)?到?(i, j)?的矩形區域的土地價值總和。
通過前綴和，可以在常數時間內計算任意矩形區域的總和。

滑動窗口計算最大值：

遍歷所有可能的首都左上角坐標?(x, y)，計算以?(x, y)?為左上角、邊長為?C?的正方形區域的總價值。
記錄最大值及其對應的坐標。

優化：

使用二維前綴和可以將矩形區域的求和從?O(C^2)?優化到?O(1)，整體復雜度為?O(N * M)。

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 C = input.nextInt();int[][] grid = new int[N + 1][M + 1]; // 地圖，1-based 索引for (int i = 1; i <= N; i++) {for (int j = 1; j <= M; j++) {grid[i][j] = input.nextInt();}}// 構建二維前綴和int[][] prefix = new int[N + 1][M + 1];for (int i = 1; i <= N; i++) {for (int j = 1; j <= M; j++) {prefix[i][j] = grid[i][j]+ prefix[i - 1][j]+ prefix[i][j - 1]- prefix[i - 1][j - 1];}}// 滑動窗口尋找最大價值int maxSum = Integer.MIN_VALUE;int bestX = 0, bestY = 0;for (int i = C; i <= N; i++) {for (int j = C; j <= M; j++) {// 計算以 (i, j) 為右下角，邊長為 C 的正方形的總價值int total = prefix[i][j]- prefix[i - C][j]- prefix[i][j - C]+ prefix[i - C][j - C];if (total > maxSum) {maxSum = total;bestX = i - C + 1;bestY = j - C + 1;}}}// 輸出結果System.out.println(bestX + " " + bestY);input.close();}
}

P3017 [USACO11MAR] Brownie Slicing G

解題思路

?前綴和計算?
構建二維前綴和數組s，其中s[i][j]表示從(1,1)到(i,j)的子矩陣和。通過前綴和，可以快速計算任意子矩陣的和，例如行區間[now+1, i]和列j的和為：
(s[i][j] - s[i][j-1]) - (s[now][j] - s[now][j-1])。

?二分答案?
在可能的范圍[0, 矩陣總和]內進行二分查找，尋找最大的x，使得矩陣可以被切割成a行b列，每塊的和均≥x。

?檢查函數check

?逐行掃描?：從第一行開始，累計當前行與上一次切割行之間的列差值。
?動態切割?：當累計值≥x時切割一列，并統計當前行切割出的列數。若某行切割出至少b列，則記為該行有效，并更新切割位置。
?結果判定?：若有效行數≥a，則當前x可行。

import java.io.*;
import java.util.*;public class Main {static int r, c, a, b; // 矩陣行數、列數，目標切割成a行b列static int[][] map = new int[501][501]; // 輸入的矩陣數據（1-based）static int[][] s = new int[501][501]; // 二維前綴和數組（1-based）static int ans; // 存儲最終結果static boolean check(int x) {int now = 0; // 記錄上一次切割的行號（初始從第0行開始）int num = 0; // 統計已切割的行數for (int i = 1; i <= r; i++) { // 遍歷每一行int dis = 0; // 當前累計的差值int sum = 0; // 當前行切割出的列數for (int j = 1; j <= c; j++) {// 計算第j列在[now+1, i]行之間的和：當前行j列前綴和 - 上一次切割行j列前綴和int current = (s[i][j] - s[i][j - 1]) - (s[now][j] - s[now][j - 1]);if (dis + current < x) { // 累加后仍不足x，繼續累積dis += current;} else { // 累積足夠，切割一列sum++;dis = 0; // 重置累計值}}if (sum >= b) { // 當前行能切割出至少b列now = i; // 更新切割行num++; // 增加切割行計數}}return num >= a; // 是否滿足至少a行}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());r = Integer.parseInt(st.nextToken());c = Integer.parseInt(st.nextToken());a = Integer.parseInt(st.nextToken());b = Integer.parseInt(st.nextToken());// 讀取矩陣數據（1-based）for (int i = 1; i <= r; i++) {st = new StringTokenizer(br.readLine());for (int j = 1; j <= c; j++) {map[i][j] = Integer.parseInt(st.nextToken());}}// 計算二維前綴和數組s[i][j]（1-based）for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {s[i][j] = s[i - 1][j] + s[i][j - 1] + map[i][j] - s[i - 1][j - 1];}}int h = 0; // 二分左邊界（最小可能值）int t = s[r][c]; // 二分右邊界（矩陣總和，最大可能值）ans = 0;// 二分查找尋找最大可行的xwhile (h <= t) {int mid = (h + t) / 2;if (check(mid)) { // 當前mid可行，嘗試更大的值ans = mid;h = mid + 1;} else { // 不可行，減小閾值t = mid - 1;}}System.out.println(ans);}
}

P3406 海底高鐵

解題思路

輸入處理：讀取城市數量和訪問順序，以及每段鐵路的票價信息。

差分數組：使用差分數組來高效統計每段鐵路的經過次數。差分數組可以在O(1)時間內處理區間增操作，最后通過前綴和得到每段鐵路的實際經過次數。

費用計算：根據每段鐵路的經過次數，比較購買紙質車票和使用IC卡的總費用，選擇較小的那個累加到總費用中。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;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]);line = br.readLine().split(" ");int[] P = new int[M];for (int i = 0; i < M; i++) {P[i] = Integer.parseInt(line[i]);}int[] d = new int[N + 2]; // 差分數組，索引0到N+1for (int j = 0; j < M - 1; j++) {int u = P[j];int v = P[j + 1];int l = Math.min(u, v);int r = Math.max(u, v) - 1;d[l]++;if (r + 1 <= N) {d[r + 1]--;}}int[] cnt = new int[N + 1]; // 段i的次數是cnt[i]int sum = 0;for (int i = 1; i <= N - 1; i++) {sum += d[i];cnt[i] = sum;}long total = 0;for (int i = 1; i <= N - 1; i++) {line = br.readLine().split(" ");int A = Integer.parseInt(line[0]);int B = Integer.parseInt(line[1]);int C = Integer.parseInt(line[2]);int k = cnt[i];if (k == 0) {continue;}long cost1 = (long) k * A;long cost2 = (long) k * B + C;total += Math.min(cost1, cost2);}System.out.println(total);}
}

P1083 [NOIP 2012 提高組] 借教室

解題思路

?差分數組原理?

?核心思想?：將區間操作轉換為端點標記
當處理訂單[l,r]增加d時：
diff[l] += d：表示從l開始所有元素增加d
diff[r+1] -= d：表示從r+1開始取消這個增加

?前綴和計算?：最終通過計算diff數組的前綴和，得到每個位置的實際變化量

?二分查找優化?

?搜索目標?：第一個導致資源不足的訂單（最小的非法訂單號）
?循環不變量?：保持[0,left)區間合法，[left,right)區間待檢查
?終止條件?：當left == right時，left即為第一個非法訂單索引

?大數處理方案?

?數據類型選擇?：
rest/diff/dArr使用long類型：防止處理1e9級數值時溢出
current使用long類型：防止累加過程溢出int范圍

?輸入處理優化?：使用(long)st.nval直接讀取浮點數轉long，保留完整精度

import java.io.*;
import java.util.*;public class Main {static int n, m; // 天數、訂單數static long[] rest; // 每日可用教室數（1-based）static long[] diff; // 差分數組（記錄每日變化量）static long[] dArr; // 訂單需求量數組（long防溢出）static int[] lArr; // 訂單左端點數組static int[] rArr; // 訂單右端點數組static boolean isValid(int x) {Arrays.fill(diff, 0); // 重置差分數組// 應用前x個訂單到差分數組for (int i = 0; i < x; i++) {int l = lArr[i];diff[l] += dArr[i]; // 區間起點增加需求if (rArr[i] + 1 <= n) { // 防止越界diff[rArr[i] + 1] -= dArr[i]; // 區間終點后一位減少需求}}// 2. 計算每日累計需求并驗證long current = 0; // 使用long防止累加溢出for (int i = 1; i <= n; i++) {current += diff[i]; // 計算前綴和得到實際需求if (current > rest[i]) { // 發現資源不足return false;}}return true;}public static void main(String[] args) throws IOException {// 輸入加速：使用StreamTokenizer處理大輸入StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));st.nextToken(); n = (int) st.nval; // 天數st.nextToken(); m = (int) st.nval; // 訂單數// 初始化每日教室數量數組（注意1-based）rest = new long[n + 2]; for (int i = 1; i <= n; i++) {st.nextToken();rest[i] = (long) st.nval;}// 存儲訂單數據（0-based）dArr = new long[m]; // 需求值存在大數，必須用longlArr = new int[m];  // 區間左端點（1-based）rArr = new int[m];  // 區間右端點（1-based）for (int i = 0; i < m; i++) {st.nextToken(); dArr[i] = (long) st.nval; // 處理大整數st.nextToken(); lArr[i] = (int) st.nval;st.nextToken(); rArr[i] = (int) st.nval;}// 初始化差分數組（大小與rest對齊）diff = new long[n + 2]; // 快速檢查：所有訂單都合法時直接輸出if (isValid(m)) {System.out.println(0);return;}// 二分查找核心邏輯（左閉右開區間）int left = 0, right = m; while (left < right) {int mid = (left + right) >>> 1; // 無符號右移防溢出if (isValid(mid + 1)) { // 檢查前mid+1個訂單是否合法left = mid + 1;    // 合法則嘗試更大的值} else {right = mid;       // 非法則縮小右邊界}}// 輸出第一個非法訂單編號（從1開始）System.out.println("-1");System.out.println(left + 1); }
}

P2882 [USACO07MAR] Face The Right Way G

解題思路

貪心策略：從左到右遍歷每個位置，如果發現當前牛朝后，則立即進行一次翻轉操作。這樣可以確保后面的處理不會影響到已經處理過的位置。

隊列維護：使用隊列來記錄翻轉操作的結束位置，以便在處理后續位置時能夠正確跟蹤當前翻轉的影響。

二分查找優化：通過遍歷所有可能的 K 值，找到使得操作次數最少的 K。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));int N = Integer.parseInt(br.readLine());int[] state = new int[N];// 讀取每一行狀態，將 'B' 轉換為 1，其他字符轉換為 0for (int i = 0; i < N; i++) {String line = br.readLine().trim();state[i] = line.charAt(0) == 'B' ? 1 : 0;}// 初始化答案變量，ansK 表示最優的 K 值，ansM 表示最小的翻轉次數int ansK = N;int ansM = Integer.MAX_VALUE;for (int K = 1; K <= N; K++) {Deque<Integer> queue = new ArrayDeque<>(); // 用于記錄當前翻轉區間的結束位置int current = 0; // 當前翻轉狀態的累積值int cnt = 0; // 當前翻轉次數boolean valid = true; // 標記當前 K 是否有效// 遍歷狀態數組for (int i = 1; i <= N; i++) {// 移除已經過期的翻轉區間while (!queue.isEmpty() && queue.peekFirst() <= i) {queue.pollFirst();current--;}int idx = i - 1; // 當前索引（從 0 開始）int cs = state[idx] ^ (current % 2); // 計算當前狀態是否需要翻轉if (cs == 1) { // 如果需要翻轉// 如果翻轉區間超出數組范圍，則當前 K 無效if (i + K - 1 > N) {valid = false;break;}cnt++; // 增加翻轉次數int end = i + K; // 計算翻轉區間的結束位置queue.addLast(end); // 將結束位置加入隊列current++; // 更新當前翻轉狀態}}// 如果當前 K 有效，更新最優解if (valid) {// 如果翻轉次數更少，或者翻轉次數相同但 K 更小，則更新答案if (cnt < ansM || (cnt == ansM && K < ansK)) {ansM = cnt;ansK = K;}}}System.out.println(ansK + " " + ansM);}
}

P4552 [Poetize6] IncDec Sequence

解題思路

?輸入處理?：使用BufferedReader讀取輸入，將每個元素存儲在數組a中。
?差分計算?：遍歷數組，計算相鄰元素的差值diff，并分別累加到正數總和pos或負數絕對值總和neg。
?最少操作次數?：取pos和neg的最大值，因為每次操作可以處理一個正數和一個負數單位，剩余部分需要單獨處理。
?可能的結果數?：計算pos和neg的差的絕對值加1，因為剩余的操作可以調整最終值的不同可能性。

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()); long[] a = new long[n]; for (int i = 0; i < n; i++) {a[i] = Long.parseLong(br.readLine());}// 計算差分數組中正差和負差的絕對值和long pos = 0; // 存儲所有正差的總和（a[i] - a[i-1] > 0）long neg = 0; // 存儲所有負差的絕對值總和（a[i] - a[i-1] < 0）for (int i = 1; i < n; i++) {long diff = a[i] - a[i - 1]; // 計算當前元素與前一個元素的差值if (diff > 0) {pos += diff; // 累加正差} else {neg += -diff; // 累加負差的絕對值（取反后相加）}}// 計算最少操作次數：等于正差和負差中較大的那個（每次操作可以抵消一個正差和一個負差）long operations = Math.max(pos, neg);// 計算可能的結果種數：正差與負差的差值絕對值 + 1（剩余的操作次數可以自由分配到不同位置）long variations = Math.abs(pos - neg) + 1;System.out.println(operations); // 輸出最少操作次數System.out.println(variations); // 輸出可能的結果種數}
}

P3029 [USACO11NOV] Cow Lineup S

解題思路

?數據結構定義?：

Cow類用于存儲每頭牛的坐標和品種，并實現Comparable接口以便根據坐標排序。

?輸入處理與排序?：

使用BufferedReader讀取輸入數據，將每頭牛的信息存入數組，并統計所有不同品種。
根據牛的坐標對數組進行排序，確保后續滑動窗口處理的有序性。

?滑動窗口邏輯?：

?初始化?：左指針left、品種計數器count、最小窗口長度minLength和品種計數哈希表breedCount。
?右指針移動?：遍歷每頭牛（作為窗口右端點），更新品種計數。當某品種首次出現時，增加計數器。
?窗口收縮?：當窗口包含所有品種時，不斷右移左指針以縮小窗口，并更新最小窗口長度。左指針移動時，減少對應品種的計數，若某品種計數歸零則減少計數器。

import java.io.*;
import java.util.*;public class Main {// 定義Cow類，存儲牛的坐標和品種，并實現Comparable接口以便排序static class Cow implements Comparable<Cow> {int x;int breed;public Cow(int x, int breed) {this.x = x;this.breed = breed;}// 按x坐標升序排序@Overridepublic int compareTo(Cow o) {return Integer.compare(this.x, o.x);}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());Cow[] cows = new Cow[n];Set<Integer> breeds = new HashSet<>(); // 用于統計所有不同的品種// 讀取輸入并初始化牛的數組for (int i = 0; i < n; i++) {StringTokenizer st = new StringTokenizer(br.readLine());int x = Integer.parseInt(st.nextToken());int breed = Integer.parseInt(st.nextToken());cows[i] = new Cow(x, breed);breeds.add(breed);}Arrays.sort(cows); // 按x坐標排序int k = breeds.size(); // 不同品種的總數if (k == 1) { // 特殊情況：只有一種品種，無需移動System.out.println(0);return;}int left = 0; // 滑動窗口左指針int count = 0; // 當前窗口中不同品種的數量long minLength = Long.MAX_VALUE; // 最小窗口長度Map<Integer, Integer> breedCount = new HashMap<>(); // 記錄窗口中各品種的出現次數for (int right = 0; right < n; right++) {int currentBreed = cows[right].breed;// 更新當前品種的計數breedCount.put(currentBreed, breedCount.getOrDefault(currentBreed, 0) + 1);if (breedCount.get(currentBreed) == 1) { // 首次出現該品種，增加計數器count++;}// 當窗口包含所有品種時，嘗試縮小窗口以找到最小長度while (count == k) {// 計算當前窗口的x坐標差，并更新最小值minLength = Math.min(minLength, cows[right].x - cows[left].x);int leftBreed = cows[left].breed;// 左指針右移，更新品種計數breedCount.put(leftBreed, breedCount.get(leftBreed) - 1);if (breedCount.get(leftBreed) == 0) { // 該品種在窗口中不再存在，減少計數器count--;}left++;}}System.out.println(minLength);}
}

P1904 天際線

解題思路

?事件處理?：

每個建筑生成兩個事件：左邊緣（開始）和右邊緣（結束）。
事件按x坐標升序排序，同一x下開始事件優先處理，確保正確的覆蓋順序。

?高度管理?：

使用TreeMap維護當前活動的高度及其出現次數，便于快速獲取最大值（lastKey()）。

?輪廓線生成?：

遍歷處理所有事件，每次處理同一x的所有事件后檢查當前最大高度。
僅當高度變化時記錄轉折點，避免冗余點。

?輸出格式?：

結果列表按順序拼接為字符串，符合題目要求的交替x和y坐標格式。

import java.io.*;
import java.util.*;public class Main {static class Event {int x;int h;boolean isStart;public Event(int x, int h, boolean isStart) {this.x = x;this.h = h;this.isStart = isStart;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));List<Event> events = new ArrayList<>();String line;// 讀取所有建筑數據并生成事件列表while ((line = br.readLine()) != null && !line.isEmpty()) {StringTokenizer st = new StringTokenizer(line);int L = Integer.parseInt(st.nextToken());int H = Integer.parseInt(st.nextToken());int R = Integer.parseInt(st.nextToken());events.add(new Event(L, H, true));    // 開始事件events.add(new Event(R, H, false));   // 結束事件}// 事件排序：按x升序，同一x下開始事件優先Collections.sort(events, (a, b) -> {if (a.x != b.x) return a.x - b.x;// 開始事件排在結束事件前面if (a.isStart && !b.isStart) return -1;if (!a.isStart && b.isStart) return 1;return 0;});TreeMap<Integer, Integer> heightCount = new TreeMap<>();List<Integer> result = new ArrayList<>();int prevHeight = 0;int i = 0;while (i < events.size()) {int currentX = events.get(i).x;// 處理同一x的所有事件int j = i;while (j < events.size() && events.get(j).x == currentX) {Event event = events.get(j);if (event.isStart) {// 添加高度計數heightCount.put(event.h, heightCount.getOrDefault(event.h, 0) + 1);} else {// 減少高度計數，若為0則移除int cnt = heightCount.getOrDefault(event.h, 0);if (cnt == 1) {heightCount.remove(event.h);} else if (cnt > 1) {heightCount.put(event.h, cnt - 1);}}j++;}// 計算當前最大高度int currHeight = heightCount.isEmpty() ? 0 : heightCount.lastKey();if (currHeight != prevHeight) {result.add(currentX);result.add(currHeight);prevHeight = currHeight;}i = j; // 移動到下一個x的事件}// 構建輸出字符串StringBuilder sb = new StringBuilder();for (int k = 0; k < result.size(); k++) {if (k > 0) sb.append(" ");sb.append(result.get(k));}System.out.println(sb);}
}

P4375 [USACO18OPEN] Out of Sorts G

解題思路

??數據結構定義??：Data類用于保存元素的值（val）和原始位置（num），并實現Comparable接口以支持排序。
??輸入處理??：讀取輸入數據并構建Data數組，使用1-based索引以匹配原C++代碼邏輯。
??排序操作??：使用Arrays.sort對數組的1到n部分進行排序，排序規則按值和原始位置升序排列。
??標記數組與計數??：vis數組用于標記元素的原始位置是否被處理。cnt記錄當前需要處理的元素數，ans記錄最大的cnt值，即最大“moo”次數。
??遍歷與更新邏輯??：遍歷排序后的數組，根據元素原始位置和當前位置的關系更新計數，并維護最大計數值。

import java.util.*;// 定義數據結構，保存元素的值和原始位置
class Data implements Comparable<Data> {int val;int num;public Data(int val, int num) {this.val = val;this.num = num;}// 實現比較方法：先按值升序，值相同則按原始位置升序@Overridepublic int compareTo(Data other) {if (this.val != other.val) {return Integer.compare(this.val, other.val);} else {return Integer.compare(this.num, other.num);}}
}public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();// 使用1-based索引，數組大小為n+1以便直接使用1到n的索引Data[] a = new Data[n + 1];for (int i = 1; i <= n; i++) {int val = input.nextInt();a[i] = new Data(val, i); // 記錄元素的原始位置（從1開始）}// 對數組的1到n部分進行排序Arrays.sort(a, 1, n + 1);// 初始化訪問標記數組，記錄每個位置是否被處理過boolean[] vis = new boolean[n + 2]; // 防止越界int cnt = 0;int ans = 1; // 至少會有一個moo輸出for (int i = 1; i <= n; i++) {// 如果當前元素的原始位置在當前位置之后，需要處理if (i < a[i].num) {cnt++;}// 如果當前位置已被訪問過，減少計數（可能已處理完畢）if (vis[i]) {cnt--;}// 標記當前元素的原始位置已被處理vis[a[i].num] = true;// 更新最大計數，即最大的moo次數ans = Math.max(ans, cnt);}System.out.println(ans);input.close();}
}

P5937 [CEOI 1999] Parity Game

解題思路

?Query類?：存儲每個查詢的x、y坐標和奇偶性z。
?并查集實現?：
find函數：路徑壓縮優化，確保快速查找根節點。
union函數：合并兩個集合。

?離散化處理?：
使用TreeSet收集所有出現的坐標點并排序。
將坐標映射到連續的索引，縮小數據范圍。

?處理查詢?：
將每個查詢的坐標轉換為離散化后的索引。
根據奇偶性類型（z），合并對應的節點并檢查矛盾。若發現矛盾立即輸出當前查詢索引。

?輸出結果?：若所有查詢均無矛盾，輸出查詢總數m。

import java.util.*;
import java.io.*;public class Main {static class Query {int x, y, z;Query(int x, int y, int z) {this.x = x;this.y = y;this.z = z;}}static int[] parent;static int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路徑壓縮}return parent[x];}static void union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {parent[fx] = fy;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());int m = Integer.parseInt(br.readLine());Query[] queries = new Query[m];Set<Integer> points = new TreeSet<>();// 讀取所有查詢并收集坐標點for (int i = 0; i < m; i++) {String[] parts = br.readLine().split(" ");int x = Integer.parseInt(parts[0]) - 1; // 轉換為前綴差形式int y = Integer.parseInt(parts[1]);int z = parts[2].equals("odd") ? 1 : 0;queries[i] = new Query(x, y, z);points.add(x);points.add(y);}// 離散化處理List<Integer> sorted = new ArrayList<>(points);int size = sorted.size();parent = new int[size * 2 + 2]; // 每個點對應兩個節點// 初始化并查集for (int i = 0; i < parent.length; i++) {parent[i] = i;}// 處理每個查詢for (int i = 0; i < m; i++) {Query q = queries[i];int x = Collections.binarySearch(sorted, q.x);int y = Collections.binarySearch(sorted, q.y);x = x < 0 ? -x - 1 : x; // 處理binarySearch的返回值y = y < 0 ? -y - 1 : y;int xSame = x;int xDiff = x + size;int ySame = y;int yDiff = y + size;if (q.z == 0) { // even: x和y奇偶性相同if (find(xSame) == find(yDiff)) {System.out.println(i);return;}union(xSame, ySame);union(xDiff, yDiff);} else { // odd: x和y奇偶性不同if (find(xSame) == find(ySame)) {System.out.println(i);return;}union(xSame, yDiff);union(xDiff, ySame);}}System.out.println(m);}
}