第16届 Java A组 省赛 真题 暴力拆解
在蓝桥杯省赛中，填空题或者简单编程题这类题目的数据范围通常允许我们直接暴力枚举。
千万不要把简单的问题复杂化，能暴力跑出来的绝不动脑子推公式，这就是“暴力拆解”的核心精神。
填空题：数位倍数
解题思路（暴力枚举）
一看数据范围：1 \sim 202504。
也就是 20 万的数据量。计算机一秒钟能算 1 亿次（10^8），20 万（2 \times 10^5）对计算机来说就是一眨眼的事。
策略：
- 写一个
for循环，从 1 遍历到 202504。 - 对于每一个数，算出它的各位数字之和。
- 怎么算？用
while循环，每次模 10 (%10) 取个位，再除 10 (/10) 删个位。
- 怎么算？用
- 判断这个和能不能被 5 整除 (
sum % 5 == 0)。 - 如果能，计数器
count加 1。
参考代码
public class Main {
public static void main(String[] args) {
int count = 0;
int n = 202504;
for (int i = 1; i <= n; i++) {
if (isDigitSumMultipleOf5(i)) {
count++;
}
}
System.out.println(count);
}
// 辅助函数：判断各数位之和是否是5的倍数
public static boolean isDigitSumMultipleOf5(int num) {
int sum = 0;
int temp = num;
while (temp > 0) {
sum += temp % 10; // 取出最后一位累加
temp /= 10; // 删掉最后一位
}
return sum % 5 == 0;
}
}
填空题：2025
解题思路（暴力枚举 + 计数检查）
一看数据范围：1 \sim 20250412。
大概是 2000 万的数据量。
- 2000 万次循环，每次循环里做一个简单的数位拆解（最多8位数，拆8次）。
- 总计算量大约 1.6 \times 10^8 次。
- Java 通常 1 秒可以跑 1 \sim 5 亿次简单运算。这个数据量在 1秒左右 是能跑完的，属于暴力法的极限安全区。
策略：
- 直接遍历：从 1 到 20250412。
- 数位统计：对于每个数，统计它里面有几个
0，几个2，几个5。- 注意：不要用
String.valueOf(i).contains(...)或者转成字符数组。虽然写起来方便，但转字符串会产生大量临时对象，2000 万次转换可能会导致超时 (TLE) 或者内存溢出。 - 推荐做法：还是用整数取模 (
%10) 的方式，纯数学运算最快。
- 注意：不要用
- 判断条件：
count[0] >= 1count[2] >= 2count[5] >= 1- 只要满足这三个条件，就是我们要找的数。
参考代码
public class Main {
public static void main(String[] args) {
int count = 0;
int max = 20250412;
for (int i = 1; i <= max; i++) {
if (check(i)) {
count++;
}
}
System.out.println(count);
}
// 检查是否包含至少1个0，2个2，1个5
public static boolean check(int num) {
int c0 = 0, c2 = 0, c5 = 0;
while (num > 0) {
int digit = num % 10;
if (digit == 0) c0++;
else if (digit == 2) c2++;
else if (digit == 5) c5++;
num /= 10;
}
// 题目要求：改变顺序后能变成2025
// 这意味着只要原料够就行：至少1个0，2个2，1个5
return c0 >= 1 && c2 >= 2 && c5 >= 1;
}
}
提示：
如果是填空题，你可以在本地跑几秒甚至几十秒都没关系，怎么写都行。但如果是编程题（提交到系统评测），遇到 2000 万这种级别的数据，千万尽量避免把数字转成 String，要养成用 x % 10 取数的习惯，速度快十倍不止。
这道题是一道非常纯粹的模拟题。既然是“省赛暴力拆解”，我们就不需要想任何复杂的数学优化，题目让我们做什么，我们就老老实实地模拟做什么，因为数据范围允许我们这样做。
变换数组
解题思路
- 观察数据范围：
- N \leq 1000（数组不大）。
- M \leq 5（变换次数非常少，只有 5 次）。
- a_i 初始值 \leq 1000。
- 结论：直接写两层循环暴力模拟即可。外层循环 m 次，内层循环遍历数组。
- 核心操作：
- 题目要求：a_i = a_i \times \text{bitCount}(a_i)。
- 在 Java 中，求一个数的二进制中有多少个 1，可以直接调用标准库函数：
Long.bitCount(val)或Integer.bitCount(val)。这是省赛必须知道的 API，比自己写循环快且不易出错。
- 避坑指南（关键点）：
- 虽然初始数字最大只有 1000，且只变换 5 次，但我们可以简单估算一下：
- 假设数字变成了 10^8，它的二进制 1 的个数大概在 10~20 之间。
- 每次乘以十几，连续乘 5 次，数字增长是指数级的。
- 虽然大概率
int也能存下（视具体测试数据而定），但在算法竞赛中，涉及连乘操作，为了保险起见，一律建议使用long类型，防止溢出。
- 虽然初始数字最大只有 1000，且只变换 5 次，但我们可以简单估算一下：
参考代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 1. 读取 N
int n = sc.nextInt();
// 2. 读取数组
// 注意：为了防止连乘后数据溢出 int 范围，这里直接用 long 数组
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextLong();
}
// 3. 读取变换次数 M
int m = sc.nextInt();
// 4. 开始暴力模拟
// 外层循环：控制变换的轮数 (一共 m 次)
for (int k = 0; k < m; k++) {
// 内层循环：遍历数组每个元素进行变换
for (int i = 0; i < n; i++) {
// 核心步骤：
// 1. 计算当前数字二进制中 1 的个数
// Java 自带神器：Long.bitCount()，不需要自己写循环去模
long bits = Long.bitCount(arr[i]);
// 2. 更新当前元素
arr[i] = arr[i] * bits;
}
}
// 5. 输出结果
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
备选方案（如果你记不住 bitCount 函数）
如果你在考场上忘记了 Long.bitCount 这个 API，可以用下面这个通用方法来代替：
// 手动计算二进制中 1 的个数
public static long myBitCount(long x) {
long count = 0;
while (x > 0) {
if (x % 2 == 1) { // 如果最后一位是 1
count++;
}
x /= 2; // 右移一位（删掉最后一位）
}
return count;
}
最短距离
这道题是非常经典的贪心算法入门题。对于这道题，最直观的、不用动脑筋的“排序后一一对应”的方法，恰好就是最优解。
解题思路（贪心策略）
这道题的核心逻辑可以概括为一句话：“顺瓜摸藤，不要交叉”。
1. 直观理解
想象一下，如果我们在数轴上有两个显示器（位置 1 和 10）和两个插座（位置 2 和 9）。
- 方案 A（交叉连接）：1 连 9，10 连 2。
- 距离：|1-9| + |10-2| = 8 + 8 = 16。
- 方案 B（顺序连接）：1 连 2，10 连 9。
- 距离：|1-2| + |10-9| = 1 + 1 = 2。
显而易见，方案 B 省得多。
2. 贪心结论
在一个一维坐标轴上，要让总连接距离最短，必须让最左边的显示器连最左边的插座，第二左边的连第二左边的……以此类推。
也就是说：大配大，小配小。
3. 算法步骤
- 把所有显示器的坐标读进来，放到一个数组里，从小到大排序。
- 把所有插座的坐标读进来，放到另一个数组里，从小到大排序。
- 遍历数组，计算对应位置的距离差（绝对值），累加起来就是答案。
4. 避坑指南（重点！）
- 数据范围：x_i, y_i 最大可达 10^9（10亿）。虽然单个坐标和单个距离可以用
int存下，但是 N 最大有 50000。 - 累加溢出：50000 \times 10^9 会达到 5 \times 10^{13}，这远远超过了
int的上限（约 2 \times 10^9）。 - 结论：统计总长度的变量
ans必须使用long类型，否则只能拿一半的分。
参考代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 1. 读取 n
int n = sc.nextInt();
// 2. 读取 n 个显示器的坐标
int[] monitors = new int[n];
for (int i = 0; i < n; i++) {
monitors[i] = sc.nextInt();
}
// 3. 读取 n 个插座的坐标
int[] sockets = new int[n];
for (int i = 0; i < n; i++) {
sockets[i] = sc.nextInt();
}
// 4. 核心步骤：分别排序
// 只有排好序，才能保证“第 i 小的显示器”对应“第 i 小的插座”
Arrays.sort(monitors);
Arrays.sort(sockets);
// 5. 累加距离
// 注意：累加结果一定要用 long，防止爆 int
long totalDistance = 0;
for (int i = 0; i < n; i++) {
// 计算绝对值距离
totalDistance += Math.abs(monitors[i] - sockets[i]);
}
System.out.println(totalDistance);
}
}
复杂度分析：
- 时间复杂度：主要消耗在排序上，为 O(N \log N)。对于 N=50000，这大概是几十万次运算，轻松在 1 秒内跑完。
- 空间复杂度：O(N)，用来存储坐标。
拼好数
解题思路一（贪心策略+分类讨论）
我们将所有数字转换为它含有 6 的个数，统计到 cnt[1] \sim cnt[5] 中（\ge 6 的直接计分）。
我们要做的就是凑数。为了让好数最多，必须遵循**“先消耗难用的，保留好用的”**这一贪心原则。
1. 资源分析（谁难用？谁好用？）
- 数字 1：极难用。无法独立成组（1+1+1=3 < 6），必须依附于大数（5, 4, 3）。策略：能用掉必须先用掉。
- 数字 2：好用。可以独立成组（2+2+2=6）。策略：尽量留到最后兜底。
2. 所有拼凑方案列表（分类讨论）
我们按数字从大到小（5, 4, 3, 2）来处理，列出它们能怎么拼，并按优先级排序：
- 对于 5（缺 1）：
- 5 + 1 （优先级最高：消耗了难用的 1）
- 5 + 2
- 5 + 3
- 5 + 4
- 5 + 5
- 对于 4（缺 2）：
- 4 + 1 + 1 （优先级最高：一次消耗两个难用的 1，把好用的 2 省下来）
- 4 + 2 （次优：消耗了一个好用的 2）
- 4 + 3
- 4 + 4
- 对于 3（缺 3）：
- 3 + 1 + 2 （优先级最高：消耗了一个 1）
- 3 + 3 （次优：自产自销）
- 3 + 2 + 2 （最后选：浪费了两个好用的 2）
- 对于 2（缺 4）：
- 2 + 2 + 2 （这是 2 的最终归宿）
解题思路二（暴力DFS + 记忆化）
如果我们无法确定完美的贪心优先级（例如纠结于“4到底该带2还是带两个1”），那我们就全部试一遍！
- 定义“动作”：先把所有能凑成好数的组合方式列出来（比如 \{5,1\}, \{4,2\}, \{4,1,1\}, \dots）。
- 搜索过程：
- 看看手里剩下的牌，能打出哪些组合？
- 尝试打出组合 A，然后递归算剩下的能凑多少。
- 回溯（撤销），尝试打出组合 B，然后递归算剩下的能凑多少。
- 上面两步对每个组合都这样做，相当于：扣除资源 \to 递归下一层 \to 恢复资源（回溯）
- ……
- 在所有尝试中取最大值。
- 记忆化（优化）：因为搜索过程中会遇到很多重复状态（比如先打A再打B，和先打B再打A，剩下的牌是一样的），我们可以用一个
Map记录一下“剩下这些牌时，最多还能凑几个”，如果下次遇到同样的状态，直接查表返回，避免重复计算。
这种方法逻辑绝对正确，能保证求出理论最大值，但速度慢，适合拿部分分。
参考代码
方法一（贪心策略+分类讨论）
import java.util.Scanner;
public class Main {
static int[] cnt = new int[7];
static int ans = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
long val = sc.nextLong();
int c = countSix(val);
if (c >= 6) ans++; // 够6个直接是好数
else cnt[c]++; // 不够的入桶
}
// === 1. 处理 5 ===
// 5 优先找 1 带，没有 1 再找 2...
match(5, 1);
match(5, 2);
match(5, 3);
match(5, 4);
pair(5); // 5+5
// === 2. 处理 4 ===
// 【核心贪心】：4 优先带两个 1，而不是带一个 2
while (cnt[4] > 0 && cnt[1] >= 2) {
cnt[4]--; cnt[1] -= 2; ans++;
}
// 实在没 1 了，再带 2
match(4, 2);
// 最后只能硬凑
match(4, 3);
pair(4); // 4+4
// === 3. 处理 3 ===
// 优先 3+1+2 (消耗一个1)
while (cnt[3] > 0 && cnt[1] > 0 && cnt[2] > 0) {
cnt[3]--; cnt[1]--; cnt[2]--; ans++;
}
// 其次 3+3 (自产自销)
pair(3);
// 最后 3+2+2 (没办法了才消耗两个2)
while (cnt[3] > 0 && cnt[2] >= 2) {
cnt[3]--; cnt[2] -= 2; ans++;
}
// === 4. 处理 2 ===
// 此时 1 肯定没了，大数也没了，只剩 2 自己玩
while (cnt[2] >= 3) {
cnt[2] -= 3; ans++;
}
System.out.println(ans);
}
// 辅助：统计6的个数
static int countSix(long x) {
String s = String.valueOf(x);
int c = 0;
for (char ch : s.toCharArray()) {
if (ch == '6') c++;
}
return c;
}
// 辅助：不同数字配对 (a + b)
static void match(int a, int b) {
while (cnt[a] > 0 && cnt[b] > 0) {
cnt[a]--; cnt[b]--; ans++;
}
}
// 辅助：相同数字配对 (a + a)
static void pair(int a) {
while (cnt[a] >= 2) {
cnt[a] -= 2; ans++;
}
}
}
方法二（暴力DFS + 记忆化）
import java.util.*;
public class Main {
static int ans = 0;
// 存储所有可能的拼凑方案（如 {5,1}, {4,2}, {3,3}...）
static List<int[]> allMoves = new ArrayList<>();
// 记忆化备忘录：Key是当前资源状态，Value是该状态下能凑出的最大数量
static Map<String, Integer> memo = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] cnt = new int[6]; // 桶：下标 1~5 对应含 6 个数为 1~5 的数字
for (int i = 0; i < n; i++) {
long val = sc.nextLong();
int c = countSix(val);
if (c >= 6) ans++; // 本身就是好数，直接拿分
else cnt[c]++; // 不够的放入桶中，交给 DFS 处理
}
// 1. 预处理：生成所有合法的拼凑方案 (和 >= 6 且 个数 <= 3)
generateMoves();
// 2. 暴力搜索 + 记忆化
System.out.println(ans + dfs(cnt));
}
/**
* 深度优先搜索
* @param cnt 当前手里剩下的牌
* @return 还能凑出多少个好数
*/
static int dfs(int[] cnt) {
// 1. 生成状态 Key (例如 "[0, 2, 1, 4, 1, 0]")
String key = Arrays.toString(cnt);
// 查表：如果算过这个状态，直接返回
if (memo.containsKey(key)) return memo.get(key);
int max = 0;
// 2. 尝试每一种拼凑方案
for (int[] move : allMoves) {
// 先安全检查：资源够不够？
if (check(cnt, move)) {
// 够的话，执行扣除
for (int x : move) cnt[x]--;
// 递归找子问题的最优解 (当前这1个 + 剩下的最优解)
max = Math.max(max, 1 + dfs(cnt));
// 回溯：把扣掉的资源加回去，以便尝试下一个方案
for (int x : move) cnt[x]++;
}
}
// 3. 记录并返回
memo.put(key, max);
return max;
}
/**
* 安全检查：手里的牌够不够打出这个组合
* 注意：不能一边检查一边扣除，必须确认完全够了再返回 true
*/
static boolean check(int[] cnt, int[] move) {
// 拷贝一个临时数组用于模拟扣除
int[] temp = Arrays.copyOf(cnt, cnt.length);
for (int x : move) {
if (temp[x] > 0) {
temp[x]--;
} else {
return false; // 某一种牌不够了
}
}
return true;
}
// 辅助：生成所有可能的组合
static void generateMoves() {
// 2个数的组合
for (int i = 1; i <= 5; i++) {
for (int j = i; j <= 5; j++) {
if (i + j >= 6) allMoves.add(new int[]{i, j});
}
}
// 3个数的组合
for (int i = 1; i <= 5; i++) {
for (int j = i; j <= 5; j++) {
for (int k = j; k <= 5; k++) {
if (i + j + k >= 6) allMoves.add(new int[]{i, j, k});
}
}
}
}
// 辅助：统计数字中 6 的个数
static int countSix(long x) {
String s = String.valueOf(x);
int c = 0;
for (char ch : s.toCharArray()) if (ch == '6') c++;
return c;
}
}
甘蔗
这道题是一道典型的 线性 DP（动态规划） 题目。
既然是“暴力拆解”，我们就不整那些花里胡哨的优化（比如单调队列优化等），直接用最朴素、最直观的 DP 思路来解决。因为在省赛中，数据范围通常允许 O(N \times \text{MaxH}) 复杂度的解法。
解题思路（动态规划）
1. 为什么贪心不行？
很多同学第一反应是贪心：这一根能不能只砍一点点，刚好满足上一根的条件？
不行。因为你为了迁就上一根，把这根砍到了某个高度，可能会导致下一根死活都配不上（比如下一根很高，差值太大）。为了全局最优，我们必须记录所有可能的状态。
2. 定义状态（填表格）
我们定义一个二维数组 dp[i][j]：
- 含义：考虑到第
i根甘蔗，且把它砍成高度j时，前i根甘蔗总共 最少砍了几刀。 - 如果不合法：如果第
i根甘蔗根本不可能变成高度j（比如j > 原高度），或者没法从前一根转移过来，我们就标记为无穷大INF。
3. 状态转移（怎么填表）
假设我们要计算 dp[i][j]（第 i 根高度为 j）。
我们需要回头看第 i-1 根甘蔗。
假设第 i-1 根甘蔗的高度是 k。
题目要求：|j - k| \in B。
也就是说，k 只能等于 j - b 或者 j + b （其中 b 是集合 B 里的数）。
转移方程：
dp[i][j] = \text{本次砍伐代价} + \min(dp[i-1][k])
其中 k 必须满足合法条件。
- 本次代价：如果
j == 原高度，代价为 0；如果j < 原高度，代价为 1。
4. 算法流程
- 初始化：第一根甘蔗没有任何前置限制。对于它的每一个可能高度 0 \sim a_1，如果有砍（变矮了）代价就是 1，没砍就是 0。
- 递推：从第 2 根遍历到第 n 根。对于每一根，枚举它所有可能的高度 j，再去集合 B 里找符合条件的前一根高度 k，取最小值。
- 答案：在最后一根甘蔗的所有可能高度
dp[n][j]中找最小那个。如果是INF，说明无解，输出 -1。
解题思路二（DFS + 记忆化搜索）
对于很多同学来说，动态规划（DP） 的状态转移方程（也就是那个二维数组怎么填、循环怎么写）非常难想，容易晕。
这时候，记忆化搜索（DFS + 备忘录） 是一个绝佳的替代方案。
它的本质和 DP 一模一样，但思维方式是**“暴力递归”**：我现在选了这个高度，下一步能去哪？哪怕我不知道全局最优，我把所有路试一遍不就知道了吗？为了不超时，我拿个小本本（备忘录）记下来。
这种写法符合人类直觉，代码结构更像“模拟过程”。
思路核心：
不要去想复杂的 dp[i][j] 怎么推导。
就想象你在第 i 根甘蔗面前，你现在把它砍成了高度 h。
然后你问计算机：“喂！我都把第 i 根砍成 h 了，你帮我算算，第 i+1 根到最后一根最少还要砍几刀？”
- 定义递归函数：
dfs(index, height)- 含义：当前是第
index根甘蔗，它的高度被定为height。请返回处理完剩下所有甘蔗（从index + 1到n）所需的最小砍伐次数。
- 含义：当前是第
- 递归逻辑：
- 遍历集合 B 里的每一个差值
diff。 - 计算下一根甘蔗
index + 1可能的高度：next_h = height + diff或next_h = height - diff。 - 如果
next_h合法（0 \le next\_h \le a[index+1]），就递归调用dfs(index + 1, next_h)。 - 把下一层的返回值加上下一根甘蔗本身的砍伐代价，取最小值。
- 遍历集合 B 里的每一个差值
- 记忆化：
- 造一个
memo[index][height]数组，初始化为 -1。 - 每次进函数先查表，如果有值直接返回。算出结果后先存表再返回。
- 造一个
参考代码
方法一（动态规划)
import java.util.*;
public class Main {
// 定义一个大数表示“不可能”
static final int INF = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNext()) return;
int n = sc.nextInt();
int m = sc.nextInt();
// 1. 读取每根甘蔗的初始高度
int[] a = new int[n + 1];
int maxH = 0; // 找出所有甘蔗里的最高值，决定DP数组开多宽
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
maxH = Math.max(maxH, a[i]);
}
// 2. 读取允许的高度差集合 B
int[] B = new int[m];
for (int i = 0; i < m; i++) {
B[i] = sc.nextInt();
}
// 3. 定义 DP 数组
// dp[i][j] 表示第 i 根甘蔗高度为 j 时的最小操作次数
// 范围：i 从 1 到 n，j 从 0 到 maxH
int[][] dp = new int[n + 1][maxH + 1];
// 初始化 DP 数组为 INF
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], INF);
}
// 4. 处理第 1 根甘蔗 (Base Case)
// 第 1 根甘蔗可以砍成 0 到 a[1] 之间的任意高度
for (int j = 0; j <= a[1]; j++) {
if (j == a[1]) {
dp[1][j] = 0; // 没砍，代价0
} else {
dp[1][j] = 1; // 砍了，代价1
}
}
// 5. 开始递推 (从第 2 根开始)
for (int i = 2; i <= n; i++) {
// 枚举当前这根甘蔗可能的高度 j (不能超过原高度 a[i])
for (int j = 0; j <= a[i]; j++) {
// 计算当前这刀的代价
int currentCost = (j == a[i]) ? 0 : 1;
// 回头看前一根甘蔗 i-1
// 只有当前一根的高度 k 满足 |j - k| 在集合 B 中时，才能转移
// 即：k = j - diff 或者 k = j + diff
for (int b : B) {
// 情况1：前一根比当前矮 (k = j - b)
int k1 = j - b;
if (k1 >= 0 && k1 <= a[i - 1]) { // k1 必须在合法高度范围内
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k1] + currentCost);
}
// 情况2：前一根比当前高 (k = j + b)
int k2 = j + b;
if (k2 >= 0 && k2 <= a[i - 1]) { // k2 必须在合法高度范围内
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k2] + currentCost);
}
}
}
}
// 6. 找答案
// 检查最后一根甘蔗的所有状态，取最小值
int ans = INF;
for (int j = 0; j <= a[n]; j++) {
ans = Math.min(ans, dp[n][j]);
}
// 如果还是 INF，说明中间断了，无解
if (ans == INF) {
System.out.println(-1);
} else {
System.out.println(ans);
}
}
}
复杂度分析
- 时间复杂度：O(n \times H \times m)。
- n 是甘蔗数量。
- H 是甘蔗的最大高度。
- m 是集合 B 的大小。
- 只要 H 不超过 2000 左右，这个暴力 DP 都能稳过。
- 空间复杂度：O(n \times H)。如果要优化空间，可以用滚动数组把第一维优化掉，只存上一行和当前行，空间变为 O(H)。但在比赛中如果不超内存，建议保留二维，代码更清晰不易出错。
方法二（DFS+记忆化搜索）
import java.util.*;
public class Main {
static int n, m;
static int[] a; // 甘蔗原高度
static int[] b; // 允许的差值集合
static int[][] memo; // 备忘录
static final int INF = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
a = new int[n + 1];
int maxH = 0;
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
maxH = Math.max(maxH, a[i]);
}
b = new int[m];
for (int i = 0; i < m; i++) {
b[i] = sc.nextInt();
}
// 初始化备忘录，-1 表示没算过
memo = new int[n + 1][maxH + 1];
for (int[] row : memo) Arrays.fill(row, -1);
int ans = INF;
// 暴力尝试：第 1 根甘蔗的所有可能高度
for (int h = 0; h <= a[1]; h++) {
// 第1根的代价：如果高度变了就是1，没变就是0
int cost = (h == a[1] ? 0 : 1);
// 递归问后面最少要砍多少刀
int res = dfs(1, h);
if (res != INF) {
ans = Math.min(ans, cost + res);
}
}
System.out.println(ans == INF ? -1 : ans);
}
/**
* 记忆化搜索函数
* @param idx 当前是第几根甘蔗
* @param h 当前这根甘蔗的高度
* @return 从第 idx+1 根开始到最后，最少需要的砍伐次数
*/
static int dfs(int idx, int h) {
// Base Case: 如果已经处理完最后一根了，后面不需要再砍了，返回 0
if (idx == n) {
return 0;
}
// 查备忘录
if (memo[idx][h] != -1) {
return memo[idx][h];
}
int minCost = INF;
// 尝试集合 B 中的每一个差值，寻找下一根甘蔗可能的合法高度
for (int diff : b) {
// 下一根可能的两个高度：h - diff 和 h + diff
int[] nextHeights = {h - diff, h + diff};
for (int nextH : nextHeights) {
// 判断高度是否合法：
// 1. 不能小于 0
// 2. 不能超过下一根甘蔗的原高度 (只能砍不能接)
if (nextH >= 0 && nextH <= a[idx + 1]) {
// 计算下一根甘蔗这一刀的代价
int cost = (nextH == a[idx + 1] ? 0 : 1);
// 递归向下
int remaining = dfs(idx + 1, nextH);
if (remaining != INF) {
minCost = Math.min(minCost, cost + remaining);
}
}
}
}
// 记入备忘录并返回
return memo[idx][h] = minCost;
}
}
方法对比
- 方法一（迭代 DP）：自底向上，效率极高，没有递归开销，但下标容易搞晕。
- 方法二（记忆化搜索）：自顶向下，逻辑符合直觉（“如果我这样选，后面怎么办？”），非常好写，不容易写出 Bug。在省赛中，如果推不出 DP 方程，首选此法。
原料采购
这道题是一道结合了贪心思想和**优先队列（堆）**的经典题目。
虽然题目看起来像是一个背包问题，但由于数据范围很大（m 高达 10^9），普通的 DP 是无法解决的。我们需要通过分析“运费”和“货款”的关系来找到突破口。
解题思路
1. 读懂“运费”机制
题目的关键在于理解运费的计算方式。
- 卡车从工厂出发，必须到达某一个最远的采购点 i，然后折返。
- 无论你在途中（采购点 1 \sim i-1）买了多少东西，只要你的最远目的地是 i，那么运费就是固定的：c_i \times o。
- 决策逻辑：我们可以枚举“最远到达的采购点”。
- 假设我们最远只去第 1 家，那就在第 1 家买满 m 个（如果不够就买不到）。
- 假设我们最远去第 2 家，那运费固定为 c_2 \times o，我们可以在第 1 家和第 2 家之间，挑最便宜的 m 个商品买。
- 假设我们最远去第 i 家，运费固定，我们在前 i 家的所有库存中，挑最便宜的 m 个。
2. 暴力法的瓶颈
如果我们枚举每一个点 i 作为终点，然后把前 i 家的所有商品按价格排序取前 m 个，时间复杂度会非常高，肯定超时。
我们需要一种“动态”的方法：当我们从第 i 家走到第 i+1 家时，如何快速更新当前“最便宜的 m 个商品”？
3. 贪心 + 优先队列
我们可以维护一个大根堆（优先队列），里面存放当前我们选中的商品。
- 堆的性质：按商品价格排序，价格最高的在堆顶。
- 算法流程：
- 从近到远遍历每一个采购点 i。
- 每到一个新点，先把它的所有库存 b_i（价格 a_i）全部扔进我们的“购物车”（堆）里。
- 此时，如果“购物车”里的商品总数超过了 m，我们就把**堆顶（也就是目前购物车里最贵的）**商品丢掉。
- 为什么要丢最贵的？因为我们要总价最小，肯定优先保留便宜的。
- 一直丢，直到商品总数刚好等于 m。
- 如果商品总数等于 m，计算当前的总花费：
购物车里的商品总价 + 当前距离 * o。更新最小答案。
4. 细节处理
- 数据结构：因为库存 b_i 很大，不能把每个商品单独存进堆里（内存爆炸）。堆里的元素应该是一个对象
{价格, 剩余库存}。 - 丢弃逻辑：当需要丢弃商品时，如果堆顶的这批货数量很大，只需扣减数量；如果丢完这批还超量，就把这批货弹出堆，继续看下一批。
- 数据类型：花费可能非常大，必须全程使用
long。
解题思路二（暴力枚举终点）
这道题的暴力解法思路非常朴素，就是**“枚举终点”**。
既然我们不知道要去哪家店作为最远点划算，那我们就假设每一家店都是终点，挨个算一遍，看谁最省钱。
-
枚举终点：
我们写一个循环，从第 1 家店遍历到第 n 家店。假设当前循环到了第 i 家店，我们决定最远只走到这里。
-
固定运费：
一旦确定第 i 家店是终点，运费就锁死了，等于 第 i 家店的距离 * o。
-
贪心买货：
现在我们只能在第 1 家到第 i 家这范围内买东西。
为了省钱，我们肯定要把这 i 家店里所有的库存都拿出来，按价格从小到大排序，然后挑最便宜的前 m 个买。
-
计算总价：
货款（最便宜的 m 个） + 运费。
如果这 i 家店的总库存加起来都不到 m 个，那这个终点方案无效。
-
打擂台：
把所有合法的终点方案算出来的总花费比一比，取最小值。
这种方法比较慢，每一轮都要重新收集商品、重新排序，时间复杂度大概是 O(N^2 \log N)。对于 N \le 5000 的数据（40% 的分）是可以过的，但在 N=10^5 时会超时。不过作为省赛保底策略，足够了。
参考代码
方法一（贪心+优先队列)
import java.io.*;
import java.util.*;
public class Main {
// 定义商品批次类
static class Item implements Comparable<Item> {
long price; // 单价
long count; // 数量
public Item(long price, long count) {
this.price = price;
this.count = count;
}
// 大根堆：价格高的排前面
@Override
public int compareTo(Item other) {
return Long.compare(other.price, this.price);
}
}
public static void main(String[] args) throws IOException {
// 使用快速输入，应对 10^5 的数据量
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long m = sc.nextLong(); // 需求量 m
long o = sc.nextLong(); // 运费系数 o
// 大根堆，维护当前选中的“最便宜的m个商品”中，价格最高的那些，方便随时踢出
PriorityQueue<Item> pq = new PriorityQueue<>();
long currentTotalCount = 0; // 当前选中的商品总数
long currentGoodsCost = 0; // 当前选中的商品总价
long minTotalCost = Long.MAX_VALUE; // 最终答案
// 遍历每一个采购点
for (int i = 0; i < n; i++) {
long price = sc.nextLong();
long stock = sc.nextLong();
long distance = sc.nextLong();
// 1. 不管三七二十一，先把这家店的货全加进来
pq.add(new Item(price, stock));
currentTotalCount += stock;
currentGoodsCost += price * stock;
// 2. 如果超载了 (选了超过 m 个)，就把贵的踢出去
while (currentTotalCount > m) {
Item expensiveItem = pq.peek(); // 看一眼最贵的
long removeCount = currentTotalCount - m; // 需要踢掉多少个
if (expensiveItem.count > removeCount) {
// 情况A：这批贵的货很多，踢掉一部分就够了
expensiveItem.count -= removeCount;
currentGoodsCost -= removeCount * expensiveItem.price;
currentTotalCount -= removeCount;
} else {
// 情况B：这批贵的货很少，全部踢掉都不够(或刚好)，那就整个弹出
pq.poll(); // 弹出堆
currentGoodsCost -= expensiveItem.count * expensiveItem.price;
currentTotalCount -= expensiveItem.count;
}
}
// 3. 如果刚好凑够 m 个，计算此时的总成本
if (currentTotalCount == m) {
// 总成本 = 货款 + 运费 (当前距离 * o)
long totalCost = currentGoodsCost + distance * o;
minTotalCost = Math.min(minTotalCost, totalCost);
}
}
// 输出结果
if (minTotalCost == Long.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(minTotalCost);
}
}
}
代码关键点解析
-
PriorityQueue<Item>：这是核心。我们利用大根堆自动排序的特性，始终让价格最贵的商品浮在堆顶。一旦总数量超过 m，我们就能以 O(1) 的时间复杂度找到该扔掉谁。
-
currentTotalCount > m的循环：这是一个动态维护的过程。随着我们走得越来越远，遇到的店越来越多，我们在堆里积累的“好货”也越来越多。为了保持总数始终为 m（或者更少），我们不断地进行“优胜劣汰”——新来的便宜货挤走旧的贵货。
-
时间复杂度：
- N 个采购点，每个点进堆一次。
- 虽然有
while循环，但每个批次的商品最多“进堆一次、出堆一次”。 - 总体复杂度为 O(N \log N)，对于 10^5 的数据量，运行非常快。
-
坑点：
- 如果所有店加起来库存都不够 m，循环结束后
minTotalCost依然是初始值，要输出 -1。 - 数据范围很大，涉及价格相乘，务必用
long。
- 如果所有店加起来库存都不够 m，循环结束后
方法二（暴力枚举终点）
import java.io.*;
import java.util.*;
public class Main {
// 定义商品类，方便排序
static class Item implements Comparable<Item> {
long price; // 单价
long count; // 库存
public Item(long price, long count) {
this.price = price;
this.count = count;
}
// 按价格从小到大排序
@Override
public int compareTo(Item other) {
return Long.compare(this.price, other.price);
}
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long m = sc.nextLong();
long o = sc.nextLong();
// 存储所有店铺的信息
// prices[i], stocks[i], distances[i] 分别存第 i 家的数据
long[] prices = new long[n];
long[] stocks = new long[n];
long[] distances = new long[n];
for (int i = 0; i < n; i++) {
prices[i] = sc.nextLong();
stocks[i] = sc.nextLong();
distances[i] = sc.nextLong();
}
long minTotalCost = Long.MAX_VALUE;
// --- 暴力开始 ---
// 枚举每一家店 i 作为“最远到达的终点”
for (int i = 0; i < n; i++) {
// 1. 收集从第 0 家到第 i 家的所有商品
List<Item> cart = new ArrayList<>();
long totalStockAvailable = 0;
for (int j = 0; j <= i; j++) {
cart.add(new Item(prices[j], stocks[j]));
totalStockAvailable += stocks[j];
}
// 如果前 i 家的总库存都不够 m 个，那走到这就毫无意义，直接跳过
if (totalStockAvailable < m) {
continue;
}
// 2. 排序：把所有商品按价格从低到高排
Collections.sort(cart);
// 3. 贪心购买：挑最便宜的 m 个
long need = m;
long goodsCost = 0;
for (Item item : cart) {
if (need <= 0) break; // 买够了
// 决定买多少：看是我们需要的多，还是这家库存多
long buyCount = Math.min(need, item.count);
goodsCost += buyCount * item.price;
need -= buyCount;
}
// 4. 计算本方案总花费：货款 + 运费 (终点距离 * o)
long currentTotalCost = goodsCost + distances[i] * o;
// 5. 更新最小值
minTotalCost = Math.min(minTotalCost, currentTotalCost);
}
// 输出结果
if (minTotalCost == Long.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(minTotalCost);
}
}
}
