蓝桥杯研究生组Java竞赛从数位倍数到原料采购的深度解题策略与实战复盘作为一名长期关注算法竞赛的开发者我每年都会关注蓝桥杯这类国内顶尖赛事。今年的研究生组Java题目再次展现了命题组在平衡基础考察与思维深度上的功力。八道题目从简单的数位处理到复杂的动态规划与贪心策略几乎覆盖了算法竞赛中的核心知识点。对于参赛选手而言这不仅是一场编程能力的测试更是一次思维严密性与工程实现能力的全面检验。本文将带你深入复盘这八道题目我们不满足于简单的代码罗列而是聚焦于解题思路的构建、算法选择的权衡以及那些在考场上容易忽略的优化细节。无论你是即将参赛的选手还是希望提升算法能力的开发者相信这份融合了实战经验与深度分析的指南都能为你提供全新的视角。1. 数位倍数模拟与数学洞察的起点试题A“数位倍数”作为一道结果填空题通常被视作热身。题目要求在1至202504的范围内统计各位数字之和为5的整数倍的数的个数。最直接的思路是遍历每个数计算其数位和并判断。然而在竞赛中即使是“签到题”也值得思考是否有更优解。一个高效的Java实现关键在于数位和计算的优化。虽然本题数据规模202504允许直接的O(n log n)遍历但养成优化习惯至关重要。我们可以避免在循环中频繁创建对象并使用位运算或查表法加速。public class DigitMultiple { public static void main(String[] args) { int count 0; for (int i 1; i 202504; i) { if (digitSum(i) % 5 0) { count; } } System.out.println(count); // 输出结果 } // 快速计算十进制数位和 static int digitSum(int x) { int sum 0; while (x 0) { sum x % 10; x / 10; } return sum; } }注意对于填空题我们只需提交最终整数结果。但在编程题中类似的数位处理函数应封装好确保效率。一个常见的优化是预处理1-9的数位和即本身但对于本题循环内的除法与取模操作已足够快。深入一层我们可以从数学角度观察规律在连续的自然数序列中数位和模5的结果呈现出一定的周期性。虽然对于本题上限无需此优化但这种思维对于更大数据范围例如10^9级别的问题至关重要。你可以尝试推导每连续10个数其个位0-9循环一遍数位和模5的余数分布是均匀的吗这可以引导出基于数位DP的更通用解法框架。2. IPv6地址压缩高维动态规划的思维体操填空题B“IPv6地址压缩”将难度陡然提升。题目要求计算所有可能的IPv6地址在其“最短压缩形式”下的字符串长度总和并对10^97取模。IPv6地址有128位通常表示为8段16进制数如2001:0db8:85a3:0000:0000:8a2e:0370:7334。压缩规则有两个每段前导零可省略全零段保留一个0。至多一处连续的多个全零段可以压缩为“::”。问题的核心在于我们需要考虑所有2^128个可能的IPv6地址这是一个天文数字并计算其最短表示的长度。显然暴力枚举是不可能的。这要求我们必须通过组合数学和动态规划来计数。解题的关键转化将128位的二进制数视为8个16位的段。每个段的值在0到65535之间。我们需要统计在所有可能的地址中通过上述压缩规则能得到的最短字符串长度之和。我们可以按段处理并记录状态。一个可行的DP状态设计是dp[i][j][k]表示处理完前i段当前是否已经使用过“::”压缩j0未使用j1已使用且最后一段是否为零k0非零k1为零的情况下某种计数或长度总和。但这样还不够因为“::”压缩的效果是删除连续零段之间的冒号其节省的长度取决于连续零段的个数。更精细的状态设计需要考虑连续零段的长度。我们可以定义dp[i][c][used]其中i表示当前处理到第几段0-indexed。c表示当前连续零段的长度0到8。used表示是否已经使用过“::”压缩0或1。状态转移需要分情况讨论当前段是零还是非零并决策是否在此处开始或结束一个“::”压缩。最终我们需要对所有可能的地址即每个段可以取0-65535共65536种值进行加权求和。由于每个非零段有65535种取值零段只有1种取值转移时需要乘上相应的组合数。一个简化版的思路框架用于理解问题规模单段表示对于一个值为v的段其字符串长度len(v)是v的十六进制表示的长度去掉前导零但若v0则长度为1。总长度基础值不考虑“::”压缩时一个地址的总长度是各段长度之和加上7个冒号。“::”压缩的节省如果从第l段到第r段都是零段l r且这是整个地址中唯一被压缩的连续零段那么可以节省(r-l)个数字字符和(r-l)个冒号不实际上“::”替换了这些零段和它们之间的冒号。节省的长度是(r-l1) * 5 - 2这里需要仔细计算原本这(r-l1)个零段每个零段长度为1一个‘0’加上它们之间的(r-l)个冒号总长度为(r-l1) (r-l)。压缩后只用“::”2个字符替代所以节省了(r-l1) (r-l) - 2 2*(r-l) - 1。但注意如果连续零段在开头或结尾节省的冒号数会变化。我们需要对所有可能的地址找出其最优压缩方案即节省长度最大的那个“::”位置并将节省的长度累加到总和中。由于地址数量巨大我们必须通过DP来聚合计数。最终答案可以表示为总长度和 所有地址的无压缩长度和 - 所有地址通过最优压缩能节省的长度和。无压缩长度和容易计算共有(2^16)^8 2^128个地址每个地址有8段。对于每个位置非零值有65535种零值有1种。通过概率计算可以求出任意一段的期望长度进而求出总长度和的期望再乘以地址总数。但题目要求的是确切的总和因此需要用DP精确计数。鉴于该题的极端复杂性它完全达到了省赛填空压轴题的难度。在考场上许多选手可能会选择战略性放弃或者基于小规模模拟猜测规律。这提醒我们对于组合计数与高维DP问题平时需要大量练习以建立清晰的数学模型和状态转移能力。3. 变换数组模拟中的性能陷阱与优化策略编程题C“变换数组”看起来是一道直接的模拟题。给定一个数组进行m次变换每次变换将每个元素a[i]替换为a[i] * bitCount(a[i])其中bitCount(x)是x的二进制表示中1的个数。数据范围n ≤ 1000,m ≤ 5,a[i] ≤ 1000。最朴素的实现是进行m轮循环每轮对每个元素计算其二进制中1的个数Integer.bitCount()或自定义函数然后相乘。由于m最大为5n最大为1000运算量很小直接模拟即可通过。import java.util.Scanner; public class TransformArray { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } int m sc.nextInt(); for (int t 0; t m; t) { for (int i 0; i n; i) { arr[i] arr[i] * Integer.bitCount(arr[i]); } } // 输出结果 for (int i 0; i n; i) { System.out.print(arr[i] (i n-1 ? \n : )); } } }然而如果我们深入思考会发现一个潜在的优化点数值的增长与循环节。由于每次变换是a[i] a[i] * bitCount(a[i])而bitCount(a[i])至少为1。因此只要a[i]非零它就会不断增长。但bitCount(x)的增长相对缓慢对于int范围最大为32。当a[i]增长到一定大小后其二进制中1的个数可能稳定下来或者数值本身因为乘法而迅速溢出题目未说明取模但根据样例似乎不考虑溢出实际比赛中应使用long以防万一。更值得探讨的是如果m非常大比如10^5我们还能直接模拟吗此时可能需要寻找规律或预处理。注意到bitCount(x)是x的一个属性变换操作可以看作一个函数f(x) x * bitCount(x)。我们可以尝试研究迭代函数f的行为。例如是否存在不动点即f(x) x显然x0是一个不动点因为bitCount(0)0但注意0 * 0 0。对于正整数f(x) x且通常严格大于。除非bitCount(x)1即x是2的幂此时f(x) x。所以所有2的幂都是不动点。一旦某个数在变换中变成了2的幂它就会停止变化。因此对于大数据范围的优化策略可以是预处理每个a[i]持续应用变换直到其变为2的幂或达到某个上界记录其变换序列。由于m很大但每个数的变换序列可能很短因为数值增长很快我们可以利用记忆化或直接计算每个数在k次变换后的值。不过本题的官方数据范围较小无需此优化。提示在竞赛中即使题目数据范围小思考更大范围下的解法也是一种很好的思维训练有助于在更复杂的问题中识别模式。4. 最大数字自定义排序与大数据处理题目D“最大数字”要求将1到n的整数重新排列将其二进制表示拼接后得到一个大的二进制数使其值最大并输出该二进制数对应的十进制值。例如n3时排列3,2,1得到二进制串11101 11101即十进制29但最优排列是3,1,2得到11110 11110十进制30。核心思路这本质上是一个排序问题。我们需要确定一个比较规则使得按照这个规则降序排列后拼接得到的二进制数最大。对于两个数字a和b考虑它们的二进制串s_a和s_b。拼接方式有两种s_a s_b或s_b s_a。我们需要比较这两种拼接后得到的二进制数的大小。由于二进制串比较大小可以从高位到低位逐位比较。更高效的方法是直接计算数值拼接a在前值为a * 2^{len(b)} b拼接b在前值为b * 2^{len(a)} a其中len(x)是x的二进制表示的长度即floor(log2(x)) 1或32 - Integer.numberOfLeadingZeros(x)。因此比较函数就是比较a * 2^{len(b)} b与b * 2^{len(a)} a的大小。若前者大则a应排在b前面。实现时需要注意n最大为10000其二进制长度不超过14位因为2^1416384。但拼接后的二进制数长度可达n * 14 ≈ 140000位远远超出long的范围。因此我们需要使用BigInteger来进行大数计算和比较。排序与拼接的实现细节将1到n的整数放入数组。使用自定义比较器排序比较器基于上述的数值比较。由于涉及幂运算直接计算2^{len}可能较慢我们可以用移位操作1L len(b)但要注意使用long避免溢出并在比较时使用BigInteger。排序后按顺序拼接。拼接过程也使用BigInteger初始化ans 0对于每个数x将ans左移len(x)位然后加上x。import java.math.BigInteger; import java.util.*; public class MaxNumber { // 计算x的二进制长度 static int bitLength(int x) { return 32 - Integer.numberOfLeadingZeros(x); } // 自定义比较器 static int compare(int a, int b) { int lenA bitLength(a); int lenB bitLength(b); // 计算 a * 2^{lenB} b 与 b * 2^{lenA} a // 使用long可能溢出所以用BigInteger BigInteger val1 BigInteger.valueOf(a).shiftLeft(lenB).add(BigInteger.valueOf(b)); BigInteger val2 BigInteger.valueOf(b).shiftLeft(lenA).add(BigInteger.valueOf(a)); return val2.compareTo(val1); // 我们希望降序排列所以若val2 val1则b应排在a前面 } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); Integer[] nums new Integer[n]; for (int i 0; i n; i) nums[i] i 1; Arrays.sort(nums, (a, b) - compare(a, b)); BigInteger result BigInteger.ZERO; for (int num : nums) { int len bitLength(num); result result.shiftLeft(len).add(BigInteger.valueOf(num)); } System.out.println(result); } }深入思考为什么这样排序是最优的这实际上是一个经典的“拼接最大数”问题例如LeetCode 179. 最大数的二进制版本。其正确性基于排序的传递性需要证明若a优于b且b优于c则a优于c。在十进制下自定义比较ab与ba可以保证传递性。在二进制下由于我们比较的是数值大小同样可以证明。在竞赛中我们通常可以相信这种直观的比较规则并通过样例验证。5. 小说情节组合数学与约束满足的抽象题目E“小说”是一道有趣的思维题。有n个人物情节有三种类型“A发现B不知道真相”A≠B“A发现B知道真相”A≠B“A知道了真相”并且需要满足以下约束类型1不能在类型3之后发生对于同一对A,B。类型2不能在类型3之前发生对于同一对A,B。对于同一对A,B类型1不能在类型2之后发生。相邻两章情节类型不能相同。完全相同的情节不能出现两次即三元组类型AB唯一。目标是最大化章节数。我们需要计算在满足所有约束下最多能使用多少个不同的情节。这本质上是一个图论或组合数学的计数问题。第一步计算情节总数。类型1选择有序对 (A, B) 且 A≠B有n*(n-1)种。类型2同样n*(n-1)种。类型3每个角色一次共n种。 总情节数total 2*n*(n-1) n 2n^2 - n。第二步考虑约束对顺序的影响。 约束1、2、3是针对同一对人物 (A,B) 的三种情节之间的时序限制。它们实际上强制了对于每一对 (A,B)其三种情节的出现顺序必须是类型1 → 类型3 → 类型2。也就是说对于特定人物对类型1必须最早出现类型3在中间类型2最晚。约束4要求相邻章节类型不同。约束5要求每个情节只能用一次。第三步构建最大序列。 我们需要将所有total个情节排成一个序列满足对于每对人物顺序为1→3→2。相邻类型不同。每个情节用一次。这类似于一个调度问题我们有三种类型的任务1,2,3其中类型3的任务有n个每个角色一个类型1和2各有n*(n-1)个且对于每对人物任务1必须在任务3之前任务3必须在任务2之前。一个直观的贪心策略是尽可能交错安排不同类型的情节以避免违反约束4。由于类型3的情节数量较少n个它们可以作为“缓冲”来隔开大量的类型1和类型2情节。经过推导可以通过构造法证明最大章节数的公式为当n1时只有类型3的情节答案为1。当n2时答案为2*n*n - 3*n 4。推导思路简化不考虑约束4时最大章节数就是total 2n^2 - n。约束4要求相邻类型不同。最坏情况下如果我们把所有类型1的情节排在一起中间必须插入其他类型来隔开。类型3的情节数量有限可能不够用。通过构造一种最优排列可以证明在n2时能实现的最大章节数恰好是2n^2 - 3n 4。一种构造方法是先安排所有类型1的情节交错人物对避免连续相同然后插入类型3最后安排类型2。具体构造需要精心设计人物对的顺序。import java.util.Scanner; public class Novel { public static void main(String[] args) { Scanner sc new Scanner(System.in); long n sc.nextLong(); long ans; if (n 1) { ans 1; } else { ans 2 * n * n - 3 * n 4; } System.out.println(ans); } }这道题考察的是将实际问题抽象为组合模型并通过数学推理得出闭合解的能力。在竞赛中对于n高达10^9的数据范围必须找到公式解任何模拟或搜索都无法通过。6. 01串二进制分块与高效计数题目F“01串”定义了一个无限长的01串它是将0,1,2,3,...的二进制表示不含前导零拼接而成。即0的二进制是“0”1的二进制是“1”2的二进制是“10”3的二进制是“11”... 拼接后得到串0 1 10 11 100 101 110 111 ...实际拼接时没有空格 011011100101110111...给定一个巨大的x最大10^18求这个无限串的前x位中有多少个1。暴力法依次生成每个数的二进制并拼接统计1的个数直到总长度达到x。对于x ≤ 10^6可以接受但对于10^18完全不可行。高效解法按二进制位数分块。 观察所有正整数可以按二进制位数分组1位数1二进制“1”共1个数总长度1*11位其中1的个数为1。2位数2,3二进制“10”,“11”共2个数总长度2*24位其中1的个数每个数的最高位都是1贡献2个1低1位中0和1各出现一次贡献1个1。总计2 1 3。3位数4,5,6,7二进制“100”,“101”,“110”,“111”共4个数总长度3*412位。1的个数最高位贡献4个1低2位中所有2位二进制数00,01,10,11各出现一次其中1的个数为4 * (2/2) 4更准确低2位中每个位出现1的次数是4 * 2 / 2 4因为共有4个数*2位8位0和1各占一半。所以总1的个数为4 4 8。推广对于k位的数从2^{k-1}到2^k - 1共有count 2^{k-1}个数总长度L(k) k * 2^{k-1}。 这些数中1的个数ones(k)可以这样计算最高位每个数最高位都是1贡献count 2^{k-1}个1。剩余k-1位这些位是所有k-1位二进制数的完整循环。每个位上0和1出现的次数相等均为count * (k-1) / 2 2^{k-2} * (k-1)。 所以ones(k) 2^{k-1} (k-1) * 2^{k-2}。算法步骤确定x位包含了多少个完整的k位块。设当前累计长度len0从k1开始如果len L(k) x则加上ones(k)并更新len。直到加上下一个块会超过x设此时块位数为m。处理最后一个不完整的m位块。这个块包含的数字是从start 2^{m-1}开始的连续整数。设剩余长度r x - len。这个块中每个数字占m位。完全包含的数字个数full r / m。剩余部分长度part r % m。计算这full个完整数字中1的个数每个数字的最高位都是1贡献full个1。低m-1位这full个数字的低位恰好是0到full-1这full个数的二进制表示每个占m-1位可能不足则视为有前导零。计算从0到full-1的所有数的二进制中1的总数。这可以通过数学公式或递归计算。计算第full1个数字即start full的前part位中1的个数。需要提取该数字二进制表示的前part位从最高位开始并统计其中1的个数。计算0到N的二进制1总数 这是一个经典问题。设f(N)为0到N含的所有数的二进制表示中1的个数总和。可以通过递归计算找到不大于N的最大2的幂2^p。则f(N) p * 2^{p-1} (N - 2^p 1) f(N - 2^p)。 解释p * 2^{p-1}是0到2^p - 1中所有位除了最高位的1的个数因为每位一半是1。(N - 2^p 1)是最高位新增的1的个数从2^p到N。再加上剩余部分N - 2^p的1的个数。import java.util.Scanner; public class InfiniteString { // 计算0到n含的所有数的二进制1的总数 static long countOnesUpTo(long n) { if (n 0) return 0; int p 63 - Long.numberOfLeadingZeros(n); // 最高位位置 long power 1L p; // 2^p long bitsBelow p * (power 1); // p * 2^{p-1} long msbCount n - power 1; // 最高位贡献 return bitsBelow msbCount countOnesUpTo(n - power); } public static void main(String[] args) { Scanner sc new Scanner(System.in); long x sc.nextLong(); if (x 0) { System.out.println(0); return; } long totalOnes 0; long accumulatedLen 0; int k 1; // 处理完整的k位块 while (true) { long blockLen (long) k * (1L (k - 1)); // L(k) k * 2^{k-1} if (accumulatedLen blockLen x) break; long blockOnes (1L (k - 1)) (k - 1) * (1L (k - 2)); // ones(k) totalOnes blockOnes; accumulatedLen blockLen; k; } // 此时k是当前块的位数accumulatedLen是之前完整块的总长度 long remaining x - accumulatedLen; if (remaining 0) { System.out.println(totalOnes); return; } // 最后一个不完整的块数字从 start 2^{k-1} 开始 long start 1L (k - 1); long fullNumbers remaining / k; long partialBits remaining % k; // 完整数字的贡献 if (fullNumbers 0) { // 最高位贡献每个完整数字最高位为1 totalOnes fullNumbers; // 低(k-1)位的贡献计算0到 fullNumbers-1 的所有数的二进制1总数 totalOnes countOnesUpTo(fullNumbers - 1); } // 部分数字的贡献 if (partialBits 0) { long num start fullNumbers; // 当前数字 // 取该数字二进制的前partialBits位从最高位开始 // 即右移 (k - partialBits) 位然后统计其中1的个数 long mask num (k - partialBits); totalOnes Long.bitCount(mask); } System.out.println(totalOnes); } }这道题是典型的数位统计问题要求选手有较强的数学归纳和位运算能力。在编写代码时特别注意long的溢出问题以及递归函数的终止条件。7. 甘蔗动态规划的状态设计与转移题目G“甘蔗”是一个序列修改问题。我们有n根甘蔗初始高度为a[i]。可以砍甘蔗将高度h变为x0 x h砍一根算一次操作。目标是使得相邻两根甘蔗的高度差|h_i - h_{i1}|属于给定的集合B大小为m。求最少操作次数若无法实现输出-1。数据范围n, m ≤ 500a[i] ≤ 1000。DP状态设计因为高度差只与相邻甘蔗有关自然想到用动态规划。定义dp[i][h]表示考虑前i根甘蔗且第i根甘蔗的最终高度为h时所需的最少操作次数。这里h的范围是0到a[i]因为只能砍不能增高。状态转移对于第i根甘蔗的某个高度h我们需要找到第i-1根甘蔗的某个高度h使得|h - h| ∈ B。然后dp[i][h] min(dp[i-1][h] cost)其中cost为将第i根甘蔗从a[i]砍到h的代价若h a[i]则为0否则为1。初始化dp[0][h]对于第一根甘蔗dp[0][h] cost(0, h)其他设为无穷大。答案min(dp[n-1][h])对所有合法的h。复杂度分析状态数n * max(a[i])最大为500 * 1000 5e5。转移时对于每个h需要检查所有可能的h使得|h-h| ∈ B。如果直接枚举h0到1000则转移复杂度为O(1000)总复杂度5e5 * 1000 5e8可能偏高。但我们可以优化对于固定的h和B中的每个差值d可能的h只有两个hd和h-d如果它们落在0到a[i-1]范围内。因此转移可以优化到O(m)总复杂度O(n * max(a) * m)最坏500*1000*5002.5e8在Java中可能处于临界但通常能通过因为很多状态不可达且常数较小。实现细节使用两个一维数组dpPrev和dpCur滚动更新节省空间。注意B集合中可能有重复或00差值意味着相邻甘蔗高度必须相等这也是允许的。无法达到的状态用一个大数如INF1e9表示。import java.util.*; public class Sugarcane { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(), m sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) a[i] sc.nextInt(); int[] B new int[m]; for (int i 0; i m; i) B[i] sc.nextInt(); int INF 1_000_000_000; int MAX_H 1000; // 根据题目 a[i] 1000 int[] dpPrev new int[MAX_H 1]; Arrays.fill(dpPrev, INF); // 初始化第一根甘蔗 for (int h 0; h a[0]; h) { dpPrev[h] (h a[0]) ? 0 : 1; } for (int i 1; i n; i) { int[] dpCur new int[MAX_H 1]; Arrays.fill(dpCur, INF); for (int h 0; h a[i]; h) { int cost (h a[i]) ? 0 : 1; for (int d : B) { // 前一根高度为 h d if (h d a[i-1]) { dpCur[h] Math.min(dpCur[h], dpPrev[h d] cost); } // 前一根高度为 h - d if (h - d 0) { dpCur[h] Math.min(dpCur[h], dpPrev[h - d] cost); } } } dpPrev dpCur; } int ans INF; for (int h 0; h a[n-1]; h) { ans Math.min(ans, dpPrev[h]); } System.out.println(ans INF ? -1 : ans); } }优化思考如果m很大比如接近500且B中的值分布稀疏上述O(m)转移已经不错。但我们可以进一步优化预处理每个高度h可能的前驱高度集合。由于B是固定的我们可以对于每个h计算出所有可能的h即h h ± d然后直接遍历这些h。但预处理也需要O(max(a) * m)相差不大。在实际比赛中实现简单清晰的版本更为重要。8. 原料采购排序与贪心的经典结合题目H“原料采购”是一个资源分配问题。有n个采购点每个点有价格a_i、库存b_i、距离c_i严格递增。卡车容量为m单位距离运费为o。我们需要选择一些采购点使得总采购量至少为m且总花费采购费 运费最小。运费只计算去程即卡车从工厂出发到最远采购点的距离L花费为L * o。关键观察如果我们确定了最远到达的采购点L即卡车行驶的距离那么所有距离不超过L的采购点都是可选的。为了最小化总花费我们应该在可选点中优先购买价格低的原料直到满足容量m。这是因为运费已经由L决定与采购点的选择顺序无关。因此算法如下将所有采购点按距离c_i升序排序题目已保证递增。从左到右遍历采购点同时维护一个数据结构如优先队列或TreeMap其中按价格升序存储当前可采购的原料及其库存。当遍历到第i个点时将其加入数据结构。然后检查当前总库存是否达到m。如果达到则从数据结构中贪心地选取价格最低的原料直到总采购量达到m计算采购总价cost_buy则当前总花费为cost_buy c_i * o。在所有这样的i中取最小值。数据结构选择我们需要支持快速插入按价格和按价格从小到大的遍历以选取最低价。TreeMapLong, Long是一个好选择键为价格值为该价格的库存总量。插入时合并相同价格的库存。选取时遍历TreeMap自然按键升序不断取出库存直到满足m。注意库存b_i和总需求m可能很大10^9所以使用long类型。import java.util.*; public class MaterialPurchase { static class Point { long price, stock, dist; Point(long a, long b, long c) { price a; stock b; dist c; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); long m sc.nextLong(), o sc.nextLong(); Point[] points new Point[n]; for (int i 0; i n; i) { points[i] new Point(sc.nextLong(), sc.nextLong(), sc.nextLong()); } // 已按距离递增给出无需排序 // Arrays.sort(points, (p1, p2) - Long.compare(p1.dist, p2.dist)); TreeMapLong, Long map new TreeMap(); // price - total stock long totalStock 0; long minCost Long.MAX_VALUE; for (int i 0; i n; i) { Point p points[i]; // 加入当前点 map.put(p.price, map.getOrDefault(p.price, 0L) p.stock); totalStock p.stock; // 如果总库存已经足够 if (totalStock m) { long need m; long buyCost 0; // 贪心选取最便宜的 for (Map.EntryLong, Long entry : map.entrySet()) { long price entry.getKey(); long stock entry.getValue(); if (need stock) { buyCost need * price; need 0; break; } else { buyCost stock * price; need - stock; } } if (need 0) { // 实际上因为 totalStock mneed肯定为0 minCost Math.min(minCost, buyCost p.dist * o); } } } System.out.println(minCost Long.MAX_VALUE ? -1 : minCost); } }复杂度分析排序O(n log n)如果未排序。遍历中每个点被加入TreeMap一次O(log n)。在贪心选取时我们可能需要遍历整个TreeMap但注意一旦我们计算了某个L对应的最小采购成本后续的L更大我们仍然需要重新计算吗上述代码在每次totalStock m时都从头遍历TreeMap最坏情况下复杂度O(n^2)对于n10^5不可接受。优化我们需要在遍历过程中动态维护当前已选点的最低采购成本。一种方法是使用两个堆一个小根堆存储价格另一个存储“待考虑”的原料。但更优雅的方法是由于我们按距离递增处理每次新增一个点后我们只需要考虑是否用新点的低价原料替换之前选的高价原料。实际上我们可以维护当前已选原料的集合按价格排序并保持总采购量恰好为m如果可能。当新点加入时将其原料插入集合。如果集合中原料总数超过m则移除价格最高的部分使总量回到m。同时不断更新当前最小采购成本。具体实现可以使用两个PriorityQueue一个最小堆存放未选择的原料按价格一个最大堆存放已选择的原料按价格。但更简单的是使用TreeMap并维护当前已选原料的总价和总量。当新点加入时将其原料加入TreeMap。然后如果总量超过m则从价格高的开始移除直到总量等于m。记录此时的总价加上当前距离运费更新答案。由于每个原料最多被加入和移除一次总复杂度O(n log n)。// 优化版本的核心循环 TreeMapLong, Long priceMap new TreeMap(); // 所有可用的原料按价格升序 long selectedAmount 0; long selectedCost 0; long minTotalCost Long.MAX_VALUE; for (Point p : points) { // 加入新原料 priceMap.put(p.price, priceMap.getOrDefault(p.price, 0L) p.stock); // 贪心选择最便宜的原料直到总量 m while (selectedAmount m !priceMap.isEmpty()) { Map.EntryLong, Long first priceMap.firstEntry(); long price first.getKey(); long stock first.getValue(); long take Math.min(stock, m - selectedAmount); selectedAmount take; selectedCost take * price; // 更新map中该价格的库存 if (stock take) { priceMap.pollFirstEntry(); } else { priceMap.put(price, stock - take); } } if (selectedAmount m) { minTotalCost Math.min(minTotalCost, selectedCost p.dist * o); // 注意不能break因为后续点可能更便宜即使距离更远 } } // 最后还需要检查是否满足条件但循环中已更新minTotalCost然而上述写法在移除原料时是从最便宜的开始拿但实际上我们应该始终保持已选集合是最便宜的m单位。当新加入的原料价格较低时可能需要替换掉已选集合中价格较高的原料。因此更正确的做法是维护一个已选集合最大堆存放价格最高的原料和一个候选集合最小堆存放未选的原料。每次加入新原料后尝试用候选集合中的低价原料替换已选集合中的高价原料。由于篇幅限制这里不展开实现。但核心思想是我们始终维护一个大小为m的已选集合按价格从高到低排序并计算其总价。当新点加入时将其原料加入候选集合。然后只要候选集合的最小价格小于已选集合的最大价格就进行替换。这样已选集合的总价会逐渐减少。同时由于距离L在增加运费在增加我们需要在所有L处检查总花费。这道题综合了排序、贪心、数据结构堆或平衡树的应用是典型的竞赛压轴题风格。在实现时要特别注意数据范围和边界条件例如m和库存可能超过int范围以及无法满足条件时输出-1。从数位处理到动态规划从组合数学到贪心优化这八道题目几乎涵盖了算法竞赛中的主要思维模式。复盘的意义不仅在于理解某一道题的解法更在于提炼出通用的解题框架如何将实际问题转化为数学模型如何设计高效的状态表示如何利用数据结构的特性进行优化。在紧张的竞赛环境中清晰的思路和稳健的代码实现缺一不可。平时训练时不妨多问自己如果数据范围扩大十倍我的算法还能工作吗是否有更优雅的数学洞察可以简化问题这种深度思考的习惯才是突破瓶颈、提升实力的关键。