顺风科技
顺风科技¶
2个小时：30道选择+2道编程
第一道：贪心¶
题目描述¶
小明有一排n个木棍，每个木棍上初始插着一些算珠，木棍从左到右依次编号为 1 2 3...n，其上的算珠数量也分别为 a1 a2 a3...an。小明认为，将这些算珠数量可以看作一个非负整数数组 \([a_1 a_2 a_3...a_n]\)，其字典序越小就越厉害。 小明可以将他的一些算珠挪一下位置，即从一根木棍上取一颗算珠下来然后放到另一根木棍上（一次操作只能移动一颗算珠）。如果他能进行最多 k 次移动操作，能得到的最小字典序的数组是怎样的。
注意，你不能从算珠数为 0 的木棍上再取走一个算珠使得数量变成-1。每个木棍上可以插无限多个算珠。 字典序：数组x的字典序小于数组y当且仅当存在一个下标i，使得xi＜yi，且xj=yj(对于1≤j＜i)。例如：\([1 2 3]＜[2 2 3] [1 2 3]＜[1 2 4]\)
样例输入 4 2 1 2 2 4 样例输出 0 1 2 6
提示
将第一根木棍的算珠移动到第四根木棍
将第二根木棍的算珠移动到第四根木棍
可以证明没有更优方案。
问题分析¶
给定一个包含 n 个木棍，每个木棍上有一些算珠，小明可以进行最多 k 次移动操作，将算珠从一根木棍移动到另一根木棍上。目标是通过最多 k 次移动操作使得木棍上的算珠数量形成一个字典序最小的数组。
解题思路¶
我们可以将这个问题看作贪心问题。为了使数组的字典序最小，优先考虑将前面的元素尽可能变小，直到无法继续优化，或者达到操作次数 k 的限制。
- 每次优先移动算珠：从字典序的角度，优先把靠前位置的算珠移到靠后的位置，因为数组的前面位置越小，字典序就越小。
- 操作的约束：每次只能移动一颗算珠，最多进行
k次。
具体步骤¶
- 尽量将靠前位置的算珠数量减少，并将这些算珠放置在靠后的位置。
- 对于每一个元素
a[i]，尽量移动到更小的数，优先减少前面的木棍上的算珠数量，直到操作次数k用完或者木棍上的算珠减少到0。 - 最终返回操作后的数组结果。
代码实现¶
import java.util.Scanner;
public class MinLexicographicalOrder {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入木棍数量 n 和最多可移动次数 k
int n = scanner.nextInt();
int k = scanner.nextInt();
// 输入木棍上算珠的初始数量
int[] beads = new int[n];
for (int i = 0; i < n; i++) {
beads[i] = scanner.nextInt();
}
// 贪心算法，尽量移动算珠，使字典序最小
for (int i = 0; i < n - 1 && k > 0; i++) {
// 能够移动的最大算珠数量
int move = Math.min(beads[i], k);
beads[i] -= move;
beads[n - 1] += move;
k -= move;
}
// 输出最终的字典序最小的数组
for (int i = 0; i < n; i++) {
System.out.print(beads[i] + " ");
}
}
}
第二题：回溯¶
题目描述¶
给定长度均为n的数组A和数组B，下标均为1到n。数组A第 i 个数记为ai，数组B第 i 个数记为bi。现在，有一个空栈C，小明可以进行两种操作：
-
当数组A不为空时，把数组A中下标最小的且尚未删除的数压入栈C中，然后从数组A中删除这个数。
-
当栈C不为空时，设当前栈C中元素个数为x，当前栈顶元素为y ，则立刻获得\({b_x}*y\) 的收益，然后把栈 C 的栈顶元素弹出。
小明的一种操作方案必须包含恰好 2n 次操作，且每次进行操作1时必须保证数组A不为空，每次进行操作2 时必须保证栈不为空。
定义一种操作方案的收益是该操作方案中所有第2种操作获得的收益之和。所有不同的操作方案的收益之和是多少。
认为两种操作方案不同，当且仅当存在至少一个j (1≤j≤2n)，满足两个方案的第 j 次操作的种类不同。
输入描述 输入第一行包含1个正整数n(1≤n≤12)，表示数组A和数组B的长度。
输入第二行包含n个正整数，第 i 个正整数是ai(1≤ai≤10) ，描述了数组A。
输入第三行包含n个正整数，第 i 个正整数是bi(1≤bi≤10) ，描述了数组B。
输出描述 输出包含一行，一个整数，表示小明所有不同的操作方案的收益之和是多少。
样例输入 2 1 2 2 3
样例输出 14
提示 样例中一共有2种操作方案：
-
操作1，操作1，操作2，操作2：该操作方案收益为23+12=8。
-
操作1，操作2，操作1，操作2：该操作方案收益为12+22=6。
上述所有操作方案的收益之和为14。
思路¶
每次操作时，有两种选择： 1. 如果数组A不为空，可以进行操作1，将元素从数组A压入栈C。 2. 如果栈C不为空，可以进行操作2，从栈C弹出元素并获得收益。
需要保证总共进行 2n 次操作，其中操作1和操作2的顺序可以动态决定，但要遵循操作的前提条件。
代码实现¶
import java.util.*;
public class MinOperationProfit {
static int totalSum = 0;
public static void calculateProfit(int n, int indexA, Stack<Integer> stack, int[] A, int[] B, int currentProfit, int operationCount) {
// 如果操作次数已经达到 2n 次，则计算总收益
if (operationCount == 2 * n) {
totalSum += currentProfit;
return;
}
// 操作1：从数组A压入栈中（数组A不为空时可以进行）
if (indexA < n) {
stack.push(A[indexA]);
calculateProfit(n, indexA + 1, stack, A, B, currentProfit, operationCount + 1);
stack.pop(); // 回溯
}
// 操作2：从栈中弹出元素并获得收益（栈C不为空时可以进行）
if (!stack.isEmpty()) {
int topElement = stack.pop();
calculateProfit(n, indexA, stack, A, B, currentProfit + B[stack.size()] * topElement, operationCount + 1);
stack.push(topElement); // 回溯
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入 n
int n = scanner.nextInt();
// 输入数组A
int[] A = new int[n];
for (int i = 0; i < n; i++) {
A[i] = scanner.nextInt();
}
// 输入数组B
int[] B = new int[n];
for (int i = 0; i < n; i++) {
B[i] = scanner.nextInt();
}
// 初始化栈
Stack<Integer> stack = new Stack<>();
// 开始递归
calculateProfit(n, 0, stack, A, B, 0, 0);
// 输出结果
System.out.println(totalSum);
}
}
-
递归的终止条件：
- 当操作次数
operationCount达到2n次时，表示该方案已经完成，累加当前方案的收益。 -
两种操作：
-
操作1：从数组A中取一个元素压入栈中，条件是
indexA < n。 - 操作2：从栈中弹出一个元素并计算收益，条件是栈不为空。
-
回溯：
-
每次操作后，都将栈的状态恢复到操作之前的状态，以便探索其他可能的方案。
- 当操作次数