今年是我第二次参加蓝桥杯软件类Java B组的比赛，这篇博客我想记录一下我对今年Java B组算法题的整体思路、解法细节、以及做题过程中遇到的一些坑和收获。希望对正在备赛或者想了解蓝桥杯题型的同学有帮助，也算是给自己的一个总结和回顾。

洛谷上整理有今年的Java B组原题，大家可以点击题目名称跳转到对应的链接查看原题或者进行测试。

1. 题目一：逃离立方塔

题目描述

小蓝一觉醒来，发现自己被困在一座高耸的塔中。这座塔共有 $2025$ 层，每一层都刻有一个数字的立方值，从底层的 $1^3,2^3,3^3,\dots$ 一直到顶层的 $2025^3$，层层叠叠，直入云霄。塔顶有一扇门，门旁刻着一行字：“若想离开此塔，需找出这些立方数中个位数字为 $3$ 的数的个数。”

小蓝非常着急，因为他需要尽快离开这座塔，去参加即将到来的蓝桥杯比赛。时间紧迫，请你帮助他解答这个问题。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

解题思路

我们只需要统计从 1 到 2025 的所有整数的立方值中，个位数字是 3 的数量。由于立方值可能超出 int 范围，需使用 long 类型来避免溢出。

此外，我们还可以通过观察立方数的个位规律进行优化。只有个位为 7 的数字，其立方的个位才为 3（因为 $7^3 = 343$，个位是 3），因此我们也可以仅统计个位为 7 的数字的个数（这种思路就不写代码了，实际上可以直接看出来是有202个）。

代码实现

public class Main {
    public static void main(String[] args) {
        int count = 0;
        for (int i = 1; i <= 2025; i++) {
            long cube = (long) i * i * i;
            if (cube % 10 == 3) {
                count++;
            }
        }
        System.out.println(count);
    }
}

2. 题目二：消失的蓝宝

题目描述

“蓝宝又不见了！” 2025 年 4 月 12 日，蓝桥杯吉祥物 “蓝宝” 在省赛前夕突然失踪。小蓝翻阅了蓝宝的活动记录，发现它的出现时间似乎与蓝桥杯的两个重要日期密切相关：

  • 第十六届省赛日期 $20250412$。
  • 第十五届省赛日期 $20240413$。

经过分析，小蓝推测蓝宝的下一次出现时间 $N$ 满足以下条件：

  1. $N + 20250412$ 能被 $20240413$ 整除。
  2. $N + 20240413$ 能被 $20250412$ 整除。

现在，请你帮小蓝找出满足条件的最小正整数 $N$，预测蓝宝的下一次出现时间。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

解题思路

将两个条件表示为：

  • N ≡ -20250412 (mod 20240413)

  • N ≡ -20240413 (mod 20250412)

这是典型的中国剩余定理求解同余方程组问题。由于两个模数互质，可以使用暴力枚举从最小满足第一个同余的数开始，每次加上 20240413，直到也满足第二个同余条件为止。

代码实现

public class Main {
    public static void main(String[] args) {
        long a = 20250412;
        long b = 20240413;

        // 求最小满足 (N + a) % b == 0
        long n = b - (a % b);
        while ((n + b) % a != 0) {
            n += b;
        }
        System.out.println(n);
    }
}

3. 题目三：电池分组

题目描述

研究员小蓝受到实验室主任的指示，需要对实验室新研发的 $N$ 个新型能量电池进行分组实验。这 $N$ 个能量电池的能量值分别用 $A_1, A_2, \dots , A_N$ 表示，每个能量值都是一个整数。为了保证实验的安全性，小蓝需要将这 $N$ 个能量电池分成两组，使得这两组能量电池的能量值异或和相等。

能量值的异或和计算方法如下：对于一个集合 $S$，其异或和等于集合中所有元素的按位异或结果。例如，集合 ${1, 2, 3}$ 的异或和为 $1 \oplus 2 \oplus 3 = 0$，其中 $\oplus$ 表示异或运算。

现在，小蓝想知道，这 $N$ 个能量电池能否分成两组，使得这两组能量电池的能量值异或和相等。注意，每组至少包含一个能量电池。

请你帮帮他！

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例占两行：

  • 第一行包含一个整数 $N$，表示能量电池的数量。
  • 第二行包含 $N$ 个整数 $A_1, A_2, \dots , A_N$，表示每个能量电池的能量值。

输出格式

对于每个测试用例，输出一行。如果可以将能量电池分成两组，使得这两组能量电池的能量值异或和相等，则输出 YES；否则，输出 NO。

输入输出样例

输入

2
3
1 2 3
4
1 2 3 4

输出

YES
NO

说明/提示

评测用例规模与约定

  • 对于 $30%$ 的评测用例，$1 \leq T \leq 10$，$2 \leq N \leq 100$，$1 \leq A_i \leq 10^3$。
  • 对于 $100%$ 的评测用例，$1 \leq T \leq 10^3$，$2 \leq N \leq 10^3$，$1 \leq A_i \leq 10^5$。

异或运算特性

  1. 异或是一个非常特殊的运算，它满足以下性质：

    • 任何数和 0 异或仍为该数：$x \oplus 0 = x$

    • 相同的两个数异或结果为 0：$x \oplus x = 0$

    • 异或运算是可交换的：$x \oplus y = y \oplus x$

    • 异或运算是结合的：$(x \oplus y) \oplus z = x \oplus (y \oplus z)$

  2. 如果将一组数分成两组，使得两组的异或和相等，实际上就是要求整个数组的异或和为 0，因为：

    • 如果整个数组的异或和是 $S$，假设可以分成两组使得两组异或和相等，则这些组的异或和都应该是 $S/2$，但是如果 $S$ 本身不为 0，是无法做到的。

因此，若数组的异或和是 0，则说明可以将其分成两组使得这两组的异或和相等，否则不可能。

解题思路

  • 对于每个测试用例，首先计算所有能量电池的异或和。

  • 如果异或和为 0，则输出 “YES”，表示可以分成两组；如果异或和不为 0，则输出 “NO”。

##代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();  // 测试用例的数量
        while (T-- > 0) {
            int N = sc.nextInt();  // 电池的数量
            int xorSum = 0;  // 用来存储异或和
            for (int i = 0; i < N; i++) {
                xorSum ^= sc.nextInt();  // 计算异或和
            }
            // 如果异或和为0，则可以分成两组，否则不可以
            if (xorSum == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        sc.close();
    }
}

4. 题目四：魔法科考试

题目描述

小明正在参加魔法科的期末考试，考生需要根据给定的口诀组合出有效的魔法。其中，老师给定了 $n$ 个上半部分口诀 $a_1, a_2, \dots , a_n$ 和 $m$ 个下半部分口诀 $b_1, b_2, \dots , b_m$，均用整数表示。完整的口诀包含一个上半部分口诀和一个下半部分口诀，当选用两个口诀 $a_i$ 和 $b_j$，将组合出完整口诀 $S = a_i + b_j$。

当 $S$ 满足 $S \leq n + m$ 且 $S$ 为质数时，魔法是有效的。魔法的种类只和 $S$ 的大小有关。如果每个上半部分口诀和每个下半部分口诀在不同的组合中可以重复使用，小明想知道一共可能组合出多少种不同的有效魔法？

输入格式

输入共三行。

  • 第一行为两个正整数 $n, m$。
  • 第二行为 $n$ 个由空格分开的正整数 $a_1, a_2, \dots , a_n$。
  • 第三行为 $m$ 个由空格分开的正整数 $b_1, b_2, \dots , b_m$。

输出格式

输出共 $1$ 行，一个整数表示答案。

输入输出样例

输入

3 4
2 3 10
3 4 5 1

输出

3

说明/提示

样例说明

可以组合出 $3,5,7$ 这三个有效魔法。

评测用例规模与约定

  • 对于 $20%$ 的评测用例，$n, m \leq 200$。
  • 对于 $60%$ 的评测用例，$n, m \leq 2000$。
  • 对于 $100%$ 的评测用例，$1\leq n, m \leq 20000$，$1\leq a_i, b_i \leq 20000$。

解题思路

我们可以通过以下步骤来解决问题：

  1. 计算可能的 $S$ 值：对于每对 $a_i$ 和 $b_j$，计算出 $S = a_i + b_j$。并且我们需要检查这个 $S$ 是否满足：

    • $S \leq n + m$

    • $S$ 是质数

  2. 使用质数筛选：由于我们需要对多个数进行质数判断，可以使用 埃拉托斯特尼筛法 来预处理所有可能的数（从 1 到 $n + m$）的质数标记。

  3. 去重：我们需要记录每个组合出的有效魔法，即每个满足条件的质数值。为了去重，可以使用集合（set）。

代码实现

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[] a = new int[n];
        int[] b = new int[m];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }

        // 计算最大可能的 S
        int maxSum = n + m;

        // 使用埃拉托斯特尼筛法计算质数
        boolean[] isPrime = new boolean[maxSum + 1];
        isPrime[0] = isPrime[1] = false; // 0 和 1 不是质数
        for (int i = 2; i <= maxSum; i++) {
            isPrime[i] = true;
        }
        
        // 筛选出质数
        for (int i = 2; i * i <= maxSum; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxSum; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 使用集合去重存储有效魔法的质数
        Set<Integer> validPrimes = new HashSet<>();

        // 遍历所有组合计算 S
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int sum = a[i] + b[j];
                if (sum <= maxSum && isPrime[sum]) {
                    validPrimes.add(sum);
                }
            }
        }

        // 输出有效魔法的数量
        System.out.println(validPrimes.size());
        sc.close();
    }
}

5. 题目五：爆破

题目描述

小明正在参加一场爆破工作。人们在地面上放置了 $n$ 个爆炸魔法阵，第 $i$ 个魔法阵的圆心坐标为 $(x_i, y_i)$，半径为 $r_i$。如果两个魔法阵相交，则它们可以一起引爆；如果两个魔法阵不相交，则可以再使用一条魔法回路将它们的边缘连接起来。小明想知道最少需要布置总长度多长的魔法回路才能使得所有的魔法阵可以一起引爆？

输入格式

输入共 $n + 1$ 行。

  • 第一行为一个正整数 $n$。
  • 后面 $n$ 行，每行三个整数表示 $x_i, y_i, r_i$。

输出格式

输出共 $1$ 行，一个浮点数表示答案（四舍五入保留两位小数）。

输入输出样例

输入

4
0 0 1
2 0 2
-3 0 1
4 4 1

输出

2.47

说明/提示

样例说明

  • 使用魔法回路连接第 $1$、$3$ 个魔法阵，长度为 $1$。
  • 使用魔法回路连接第 $2$、$4$ 个魔法阵，长度为 $2\sqrt{5} - 3 = 1.47$。

总长度 $2.47$。

评测用例规模与约定

  • 对于 $40%$ 的评测用例，$n \leq 500$。
  • 对于 $100%$ 的评测用例，$1\leq n \leq 5000$，$|x_i|, |y_i| \leq 2000$，$0 < r_i \leq 20$。

解题思路

魔法阵之间：

  • 若相交（圆与圆相交或相切），可以直接连通；

  • 若不相交，可以用一条魔法回路（即线段）将它们连接起来，花费等于两圆心的距离减去两个半径之和。

因此，我们可以将这些魔法阵看作图中的点，它们之间的“最短连接代价”看作边的权值，求最小总连接长度的问题就变成了最小生成树（Minimum Spanning Tree，MST）问题。

我们可以采用经典的 Prim 算法 来求解：

  1. 任意选择一个起点加入生成树；

  2. 每次从当前生成树中，选择一条最短的连接边将一个新节点加入；

  3. 重复该操作直到所有点都加入树中。

在计算两魔法阵间的连接长度时：

  • 如果两个魔法阵相交（两圆心距离小于等于半径之和），则不需要额外连接，代价为 0；

  • 否则，连接代价为 两圆心距离 - 两圆半径之和。

由于最多只有 5000 个魔法阵，用 Prim 算法配合数组实现可以顺利通过本题。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double[][] arr = new double[n][3]; // 存坐标和半径

        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextDouble(); // x
            arr[i][1] = sc.nextDouble(); // y
            arr[i][2] = sc.nextDouble(); // r
        }

        boolean[] visited = new boolean[n]; // 标记已连接的魔法阵
        double[] minDist = new double[n];   // 每个点与当前树的最短距离
        for (int i = 0; i < n; i++) minDist[i] = Double.MAX_VALUE;

        double totalLength = 0;
        minDist[0] = 0; // 从第一个魔法阵开始连接

        for (int i = 0; i < n; i++) {
            // 找到当前未访问且距离最小的点
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || minDist[j] < minDist[u])) {
                    u = j;
                }
            }

            visited[u] = true;
            totalLength += minDist[u];

            // 更新其它点与当前树的最小距离
            for (int v = 0; v < n; v++) {
                if (!visited[v]) {
                    double dist = getLength(
                        arr[u][0], arr[u][1], arr[u][2],
                        arr[v][0], arr[v][1], arr[v][2]
                    );
                    if (dist < minDist[v]) {
                        minDist[v] = dist;
                    }
                }
            }
        }

        System.out.printf("%.2f\n", totalLength);
    }

    // 计算两个魔法阵的“连接长度”（如果相交则为0）
    static double getLength(double x1, double y1, double r1, double x2, double y2, double r2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        double centerDist = Math.sqrt(dx * dx + dy * dy);
        double res = centerDist - (r1 + r2);
        return Math.max(0, res);
    }
}

6. 题目六：数组翻转

题目描述

小明生成了一个长度为 $n$ 的正整数数组 $a_1, a_2, \dots , a_n$，他可以选择连续的一段数 $a_l, a_{l+1}, \dots, a_r$，如果其中所有数都相等即 $a_l = a_{l+1} = \dots = a_r$，那么他可以获得 $(r - l + 1) \times a_l$ 的分数。

在选择之前，为了让分数尽可能大，他决定先选择数组中的一段区间，对其进行左右翻转。他想知道在对数组进行翻转之后他能获得的最大分数是多少？

提示：当翻转 $a_l$ 到 $a_r$ 这段区间后，整个数组会变为：

$$a_1, a_2, \dots , a_{l-1}, a_r, a_{r-1}, \dots , a_{l+1}, a_l, a_{r+1}, \dots , a_n$$

输入格式

输入共两行。

  • 第一行为一个正整数 $n$。
  • 第二行为 $n$ 个由空格分开的正整数 $a_1, a_2, \dots , a_n$。

输出格式

输出共 $1$ 行，一个整数表示答案。

输入输出样例

输入

7
4 4 3 3 2 1 3

输出

9

说明/提示

样例说明

翻转区间 $[5, 7]$，数组变为 $4, 4, 3, 3, 3, 1, 2$，最大分数为选择三个 $3$。

评测用例规模与约定

  • 对于 $20%$ 的评测用例，$n \leq 500$。
  • 对于 $100%$ 的评测用例，$1\leq n \leq 10^6$，$1\leq a_i \leq 10^6$。

解题思路

所谓翻转操作其实没必要实现，只需要对每个数统计连续出现的次数，保留最大的两个结果。最后在遍历数值乘以（两次连续出现次数和），得到最大值输出即可。

  • 比如数值为 x 的最大连续段为 a，次长为 b，翻转后有可能拼接出一段长度 a + b 的连续段，得分为 x × (a + b)。

  • 枚举所有数值，统计其前两大连续段长度 a 和 b，取最大得分即可。

代码实现

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        QReader in = new QReader();
        QWriter out = new QWriter();
        int n = in.nextInt();
        int[] arr = new int[n];
        int[][] tong = new int[1000001][2];
        
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        
        for (int i = 0; i < n; i++) {
            int c = 0;
            c++;
            while (i < n - 1 && arr[i] == arr[i + 1]) {
                i++;
                c++;
            }
            if (c > tong[arr[i]][0]) {
                tong[arr[i]][1] = tong[arr[i]][0];
                tong[arr[i]][0] = c;
            } else if (c > tong[arr[i]][1]) {
                tong[arr[i]][1] = c;
            }
        }
        
        long s = 0;
        for (int i = 0; i < 1000001; i++) {
            long t = (long) i * (tong[i][1] + tong[i][0]);
            if (t > s) s = t;
        }
        out.println(s);
        out.close();
    }
    
    static class QReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
    static class QWriter implements Closeable {
        private BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        public void print(Object object) {
            try {
                writer.write(object.toString());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        public void println(Object object) {
            try {
                writer.write(object.toString());
                writer.write("\n");
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        @Override
        public void close() {
            try {
                writer.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

7. 题目七：2的幂

题目描述

小明很喜欢 $2$ 的幂，所以他想对一个长度为 $n$ 的正整数数组 ${a_1, a_2, \dots, a_n}$ 进行改造。他可以进行如下操作任意多次（可以是 $0$ 次）：任选一个数 $a_i$ 加上任意正整数，但不能使得加完之后的结果超过 $10^5$。

在操作任意次后，小明希望所有数的乘积是 $2^k$ 的倍数。他想知道总共需要加的数的总和至少是多少？

输入格式

输入共两行。

  • 第一行为两个正整数 $n, k$。
  • 第二行为 $n$ 个由空格分开的正整数 $a_1, a_2, \dots, a_n$。

输出格式

输出共 $1$ 行，一个整数表示答案。如果不能满足条件，输出 $-1$。

输入输出样例

输入

3 9
19 10 3

输出

12

说明/提示

样例说明

将三个数分别加到 $24, 16, 4$，它们的乘积为 $1536 = 2^9 \times 3$，加的数的总和为 $5 + 6 + 1 = 12$。

评测用例规模与约定

  • 对于 $20%$ 的评测用例，$n, k \leq 10$。
  • 对于 $100%$ 的评测用例，$1\leq n \leq 500$，$1\leq k \leq 5000$，$1\leq a_i \leq 100000$。

解题思路

题目要求让所有数的乘积成为 $2^k$ 的倍数。若一个数是 $2^p$ 的倍数，另一个数是 $2^q$ 的倍数，那么它们的乘积一定是 $2^{p+q}$ 的倍数。

因此，可以把问题转化为：对每个 $a_i$ 增加尽可能少的值，使所有数中因子 $2$ 的数量之和不少于 $k$。

定义 $dp[i][j]$ 表示处理前 $i$ 个数后，使它们的乘积成为 $2^j$ 的倍数所需的最小增加量。

  • 枚举第 $i$ 个数需要成为 $2^l$ 的倍数，其中 $0 \le l \le 16$。由于修改后的数不能超过 $10^5$，只需枚举到 $16$。
  • 设 $x$ 为不小于 $a_i$ 的最小 $2^l$ 的倍数，则本次增加量为 $x-a_i$。
  • 用整数运算计算 $x$：

$$
x = \left\lceil \frac{a_i}{2^l} \right\rceil \times 2^l
$$

状态转移为：

$$
dp[i][j] = \min\left(dp[i][j],\ dp[i-1][j-l] + x-a_i\right)
$$

初始状态为 $dp[0][0]=0$，其余状态均为无穷大。若最终 $dp[n][k]$ 仍为无穷大，则无解，输出 $-1$。

时间复杂度为 $O(nk\log 10^5)$，本题中每个状态最多枚举 $17$ 次；空间复杂度为 $O(nk)$。

代码实现

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    static final int MAX_N = 505;
    static final int MAX_K = 5005;
    static final int INF = 0x3f3f3f3f;

    public static void main(String[] args) throws Exception {
        FastScanner scanner = new FastScanner();
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[] a = new int[MAX_N];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }

        int[][] dp = new int[MAX_N][MAX_K];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int l = 0; l <= Math.min(16, j); l++) {
                    int divisor = 1 << l;
                    // 不小于 a[i] 的最小 divisor 的倍数
                    int x = (a[i] + divisor - 1) / divisor * divisor;

                    if (x > 100000) {
                        break;
                    }

                    if (dp[i - 1][j - l] != INF) {
                        dp[i][j] = Math.min(
                                dp[i][j],
                                dp[i - 1][j - l] + x - a[i]
                        );
                    }
                }
            }
        }

        System.out.println(dp[n][k] == INF ? -1 : dp[n][k]);
    }

    static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int pointer = 0;
        private int length = 0;

        private int read() throws IOException {
            if (pointer >= length) {
                length = input.read(buffer);
                pointer = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[pointer++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ');

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value;
        }
    }
}

8. 题目八：研发资源分配

题目描述

在蓝桥科技公司，$A$ 部门和 $B$ 部门正在竞争一种新型 AI 芯片的研发资源。

为了公平分配资源，公司设计了一个为期 $N$ 天的分配方案：

每天早上，$A$ 部门和 $B$ 部门各自提交一个需求等级（从 $1$ 到 $N$ 的整数）。提交等级较高的部门获得当天的资源，资源份额等于当天的日期编号（第 $1$ 天为 $1$ 单位，第 $2$ 天为 $2$ 单位，依次递增）。若两部门提交的等级相同，则当天资源作废，双方均无法获得资源。

每个部门必须在 $N$ 天内使用 $1$ 到 $N$ 的所有等级，且每个等级只能使用一次。

有趣的是，$A$ 部门在 $B$ 部门内部安插了一名 “间谍”，提前获知了 $B$ 部门的需求等级提交顺序，记为排列 ($P_1, P_2, \dots , P_N$)，其中 $P_i$ 表示 $B$ 部门在第 $i$ 天提交的需求等级。

现在，请你帮助 $A$ 部门分析，在已知 $B$ 部门需求等级顺序的情况下，$A$ 部门的总资源份额减去 $B$ 部门的总资源份额的差值最大可以是多少？

输入格式

第一行包含一个整数 $N$，表示分配方案的天数。

第二行包含 $N$ 个整数 $P_1, P_2, \dots , P_N$，表示 $B$ 部门在第 $1$ 天到第 $N$ 天提交的需求等级。

输出格式

输出一个整数，表示 $A$ 部门的总资源份额减去 $B$ 部门的总资源份额的最大差值。

输入输出样例

输入

3
1 3 2

输出

2

说明/提示

样例说明

$A$ 部门可以选择排列 $[2, 1, 3]$：

  • 第 $1$ 天：$A(= 2) > B(= 1)$，$A$ 获得 $1$ 单位资源；
  • 第 $2$ 天：$A(= 1) < B(= 3)$，$B$ 获得 $2$ 单位资源；
  • 第 $3$ 天：$A(= 3) > B(= 2)$，$A$ 获得 $3$ 单位资源。

两者的差值为 $4 - 2 = 2$。

评测用例规模与约定

  • 对于 $20%$ 的评测用例，$1 \leq N \leq 11$，$1 \leq P_i \leq N$，$P_1, P_2, \dots , P_N$ 各不相同。
  • 对于 $100%$ 的评测用例，$1 \leq N \leq 10^5$，$1 \leq P_i \leq N$，$P_1, P_2, \dots , P_N$ 各不相同。

解题思路

这个题有点类似田忌赛马，但是更复杂一些，我们要做的不是单纯赢更多回合，而是赢更“值钱”的回合，或最起码让对方不得分。

  • 每一天都可以看成是一个“比赛”机会，比赛的资源份额等于当天是第几天。

  • B 部门在每一天提交了一个数字（1~N 的排列）。

  • 你可以将这些数据封装成一个结构体 node{val, pos}：

    • val 表示 B 提交的等级（1~N）

    • pos 表示第几天（资源是 pos 单位）

  • 然后我们可以 把这些结构体按照 val 从大到小排序，也就是 B 最贪的在前面。

  • 如果按照常规的田忌赛马的思路，我们可能会干脆用 1 去和 B 的最大数字对抗，让出这一天，然后保留上等马。但是如果 B 的上等马正好在最后一天，也就是说资源是最大的一天，这时如果使用下等马1，就等于把一大份资源送给了 B，这可能得不偿失。

  • 也就是说用下等马输给上等马是有用的，但要看代价是不是太大。如果代价很高（比如是第 N 天），可能就不如直接派出上等马与 B 的上等马打个平手，这样虽说我们也没分，但起码不会让 B 得太多分。

  • 正确的做法应该是排序后，模拟让前 k 个最贪的回合给对方（或者跟他打平），剩下的赢回来。

  • 在所有 k 情况下取最大值，就是最终的最优差值。

代码实现

import java.util.*;

public class Main {
    static class Node {
        int val; // B 部门提交的需求等级
        int pos; // 第几天（资源值为 pos + 1）
        Node(int val, int pos) {
            this.val = val;
            this.pos = pos;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node[] a = new Node[n];
        long total = (long) n * (n + 1) / 2; // 所有资源总和
        long sum = total;
        long ans = 0;

        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            a[i] = new Node(val, i + 1); // pos 是第几天，从 1 开始
        }

        // 按照 val 降序（B 部门需求等级高的排在前）
        Arrays.sort(a, (x, y) -> y.val - x.val);

        for (int i = 0; i < n; i++) {
            sum -= a[i].pos; // 将当天资源让给 B
            ans = Math.max(ans, sum - a[i].pos); // 更新最大差值
        }

        System.out.println(ans);
    }
}

以上就是 2025 年蓝桥杯 Java B 组全部 8 道真题的整理与解析。

蓝桥杯不仅是一次算法水平的检验，更是一次思维方式和时间管理的挑战。今年的题目让我意识到基础真的非常重要，同时也要不断锻炼自己解决陌生问题的能力。

无论最终成绩如何，这次经历都让我成长了不少。也希望这篇博客能给你带来一些启发。如果你也正在准备蓝桥杯，记得多刷真题、多做总结，相信你也一定能在赛场上发挥出自己的最佳水平！