java 洛谷题单【算法2-1】前缀和、差分与离散化

P8218 【深进1.例1】求区间和

解题思路

1. 前缀和数组：

   • prefixSum[i] 表示数组 a 的前 (i) 项的和。
   • 通过 prefixSum[r] - prefixSum[l - 1] 可以快速计算区间 ([l, r]) 的和。

2. 时间复杂度：

   • 构建前缀和数组的时间复杂度是 (O(n))。
   • 每次查询的时间复杂度是 (O(1))。
   • 总体时间复杂度从原来的 (O(m \cdot n)) 降低到 (O(n + m))。

3. 空间复杂度：

   • 额外使用了一个长度为 (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 最大加权矩形

解题思路

1. 枚举上下边界：

   • 使用两个嵌套循环 top 和 bottom，分别表示矩形的上边界和下边界。
   • 在固定上下边界后，将矩阵压缩为一维数组 temp，其中 temp[col] 表示当前上下边界内第 col 列的累加和。

2. Kadane 算法：

   • 对压缩后的一维数组 temp 使用 Kadane 算法，快速计算最大子数组和。
   • Kadane 算法的时间复杂度是 (O(n))。

3. 更新最大值：

   • 每次计算出当前上下边界内的最大子数组和后，更新全局最大值 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 提高组] 聪明的质监员

解题思路

1. 输入处理：

   • 使用 BufferedReader 和 StringTokenizer 读取输入。
   • 矿石的重量和价值存储在数组 w 和 v 中。
   • 区间的左右端点存储在数组 l 和 r 中。

2. 二分查找：

   • 使用变量 ans 表示当前的候选参数 。
   • 从高位到低位逐步尝试增加 的值，直到找到满足条件的最大 $W$。

3. 辅助函数 Y：

   • 计算当前参数 对应的检验值 。
   • 使用前缀和数组 s1 和 s2 快速计算区间内的权重和价值总和。

4. 结果计算：

   • 比较 和 ，取与 差值的最小值作为最终结果。

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 语文成绩

解题思路

1. ​差分数组​：差分数组允许我们在O(1)时间内完成区间加减操作。差分数组d的第i个元素表示原数组a中第i个元素与前一个元素的差值。
2. ​区间操作处理​：对于每个区间操作(x, y, z)，我们只需在差分数组的d[x]加上z，并在d[y+1]减去z。
3. ​前缀和计算​：通过计算差分数组的前缀和，我们可以得到每个学生的最终成绩，并找到其中的最小值。

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. ​二维差分数组​：差分数组是一种用于高效处理区间更新操作的数据结构。通过记录区间的起点和终点的变化量，我们可以在最后通过前缀和每个点的最终覆盖次数。
2. ​差分操作​：对于每个地毯覆盖的矩形区域，我们更新差分数组的四个角点，分别进行加1和减1操作。
3. ​前缀和计算​：通过两次前缀和计算（先按行，再按列），我们可以将差分数组转换为每个点的实际覆盖次数。

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 火烧赤壁

解题思路

1. 输入处理：将所有的区间存储在 List<int[]> 中，每个区间用一个长度为 2 的数组表示。

2. 排序：按区间的起点升序排序，如果起点相同，则按终点升序排序。

3. 区间合并：遍历排序后的区间列表，判断当前区间是否与前一个区间重叠：

   • 如果不重叠，则将前一个区间的长度累加到总长度中，并更新当前区间为新的起点和终点。
   • 如果重叠，则更新当前区间的结束点。

4. 输出结果：最后将最后一个区间的长度累加到总长度中。

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] 程序自动分析

解题思路

1. 初始化并查集：高效处理连通性问题，每个元素初始时是独立的集合。
2. 处理相等约束：将相等的元素合并到同一个集合。
3. 处理不等约束：
   • 检查不等的元素是否已经连通。
   • 如果连通，则违反约束，返回 NO。
4. 输出结果：如果所有约束都满足，返回 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

解题思路

1. 离散化坐标：

   • 由于坐标范围很大（-10^8 到 10^8），直接操作会导致内存和时间复杂度过高。
   • 我们可以将所有矩形的横坐标和纵坐标进行离散化，映射到一个较小的索引范围。

2. 扫描线算法：

   • 按照矩形的横坐标（x 值）排序，依次处理每个矩形的左边界和右边界。
   • 使用一个差分数组或线段树来维护当前被覆盖的纵坐标区间。

3. 计算面积：

   • 每次扫描到一个新的横坐标时，根据当前的覆盖区间计算面积增量。
   • 面积增量等于当前覆盖的纵坐标长度乘以横坐标的变化量。

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，多试几次就能过。

1. 二维前缀和：

   • 构建一个二维前缀和数组 prefix，其中 prefix[i][j] 表示从地图左上角 (1, 1) 到 (i, j) 的矩形区域的土地价值总和。
   • 通过前缀和，可以在常数时间内计算任意矩形区域的总和。

2. 滑动窗口计算最大值：

   • 遍历所有可能的首都左上角坐标 (x, y)，计算以 (x, y) 为左上角、边长为 C 的正方形区域的总价值。
   • 记录最大值及其对应的坐标。

3. 优化：

   • 使用二维前缀和可以将矩形区域的求和从 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

解题思路

1. ​前缀和计算​
   构建二维前缀和数组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])。

2. ​二分答案​
   在可能的范围[0, 矩阵总和]内进行二分查找，寻找最大的x，使得矩阵可以被切割成a行b列，每块的和均≥x。

3. ​检查函数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 海底高铁

解题思路

1. 输入处理：读取城市数量和访问顺序，以及每段铁路的票价信息。

2. 差分数组：使用差分数组来高效统计每段铁路的经过次数。差分数组可以在O(1)时间内处理区间增操作，最后通过前缀和得到每段铁路的实际经过次数。

3. 费用计算：根据每段铁路的经过次数，比较购买纸质车票和使用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 提高组] 借教室

解题思路

1. ​差分数组原理​

   • ​核心思想​：将区间操作转换为端点标记
     当处理订单[l,r]增加d时：
     • diff[l] += d：表示从l开始所有元素增加d
     • diff[r+1] -= d：表示从r+1开始取消这个增加
   • ​前缀和计算​：最终通过计算diff数组的前缀和，得到每个位置的实际变化量

2. ​二分查找优化​

   • ​搜索目标​：第一个导致资源不足的订单（最小的非法订单号）
   • ​循环不变量​：保持[0,left)区间合法，[left,right)区间待检查
   • ​终止条件​：当left == right时，left即为第一个非法订单索引

3. ​大数处理方案​

   • ​数据类型选择​：
     • 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

解题思路

1. 贪心策略：从左到右遍历每个位置，如果发现当前牛朝后，则立即进行一次翻转操作。这样可以确保后面的处理不会影响到已经处理过的位置。

2. 队列维护：使用队列来记录翻转操作的结束位置，以便在处理后续位置时能够正确跟踪当前翻转的影响。

3. 二分查找优化：通过遍历所有可能的 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

解题思路

1. ​输入处理​：使用BufferedReader读取输入，将每个元素存储在数组a中。
2. ​差分计算​：遍历数组，计算相邻元素的差值diff，并分别累加到正数总和pos或负数绝对值总和neg。
3. ​最少操作次数​：取pos和neg的最大值，因为每次操作可以处理一个正数和一个负数单位，剩余部分需要单独处理。
4. ​可能的结果数​：计算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

解题思路

1. ​数据结构定义​：

   • Cow类用于存储每头牛的坐标和品种，并实现Comparable接口以便根据坐标排序。

2. ​输入处理与排序​：

   • 使用BufferedReader读取输入数据，将每头牛的信息存入数组，并统计所有不同品种。
   • 根据牛的坐标对数组进行排序，确保后续滑动窗口处理的有序性。

3. ​滑动窗口逻辑​：

   • ​初始化​：左指针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 天际线

解题思路

1. ​事件处理​：

   • 每个建筑生成两个事件：左边缘（开始）和右边缘（结束）。
   • 事件按x坐标升序排序，同一x下开始事件优先处理，确保正确的覆盖顺序。

2. ​高度管理​：

   • 使用TreeMap维护当前活动的高度及其出现次数，便于快速获取最大值（lastKey()）。

3. ​轮廓线生成​：

   • 遍历处理所有事件，每次处理同一x的所有事件后检查当前最大高度。
   • 仅当高度变化时记录转折点，避免冗余点。

4. ​输出格式​：

   • 结果列表按顺序拼接为字符串，符合题目要求的交替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

解题思路

1. ​​数据结构定义​​：Data类用于保存元素的值（val）和原始位置（num），并实现Comparable接口以支持排序。
2. ​​输入处理​​：读取输入数据并构建Data数组，使用1-based索引以匹配原C++代码逻辑。
3. ​​排序操作​​：使用Arrays.sort对数组的1到n部分进行排序，排序规则按值和原始位置升序排列。
4. ​​标记数组与计数​​：vis数组用于标记元素的原始位置是否被处理。cnt记录当前需要处理的元素数，ans记录最大的cnt值，即最大“moo”次数。
5. ​​遍历与更新逻辑​​：遍历排序后的数组，根据元素原始位置和当前位置的关系更新计数，并维护最大计数值。

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

解题思路

1. ​Query类​：存储每个查询的x、y坐标和奇偶性z。
2. ​并查集实现​：
   • find函数：路径压缩优化，确保快速查找根节点。
   • union函数：合并两个集合。
3. ​离散化处理​：
   • 使用TreeSet收集所有出现的坐标点并排序。
   • 将坐标映射到连续的索引，缩小数据范围。
4. ​处理查询​：
   • 将每个查询的坐标转换为离散化后的索引。
   • 根据奇偶性类型（z），合并对应的节点并检查矛盾。若发现矛盾立即输出当前查询索引。
5. ​输出结果​：若所有查询均无矛盾，输出查询总数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);}
}