得物笔试 得物秋招 得物笔试题 1019
笔试时间：2025年10月19日
往年笔试合集：
第一题：训练
在遥远的国度有一位国王，在他手下有一支战无不胜的军队，但是他觉得这还不够，他决定继续通过训练提升军队的实力。军队中共有 n 名战士，其中第 i 位的战斗力为 aᵢ。在第 j 次训练中，国王会先找出战斗力最低的战士，假设他的战斗力为 x，则国王会同时训练所有战斗力为 x 的战士，将他们的战斗力都提升 bⱼ（从 x 变为 x + bⱼ）。这样的训练一共会进行 m 次。同时，为了时刻了解军队的情况，国王请你帮他计算一下，在每次训练后所有战士的战斗力之和为多少。
输入描述
第一行两个正整数 n 和 m，表示战士数量和训练次数。
第二行为 n 个正整数 aᵢ (1 ≤ i ≤ n)，其中 aᵢ 表示第 i 个战士初始的战斗力为 aᵢ。
第三行为 m 个正整数 bⱼ，其中 bⱼ 表示第 j 次训练后战斗力增加值为 bⱼ。
1 ≤ n, m ≤ 2×10⁵，1 ≤ aᵢ, bⱼ ≤ 2×10⁵，且保证每次训练后每个士兵的战斗力都不会超过 2×10⁵。
输出描述
输出一行 m 个正整数，其中第 j 个数表示第 j 次训练后所有战士的战斗力之和。
样例输入
4 2
1 1 2 3
1 3
样例输出
9 18
样例说明：
第一次训练后，战斗力为 1 的战士的战斗力全都变成 2，所有战士战斗力分别为 2、2、2、3，总和为 9。第二次训练后，战斗力为 2 的战士的战斗力全都变成 5，所有战士战斗力分别为 5、5、5、3，总和为 18。
参考题解
解题思路：
通过一个数组来统计每个战斗力数值的士兵数量，并计算出初始的总战斗力和当前的最低战斗力。在每一次训练中，程序直接定位到拥有当前最低战斗力的那批士兵，将他们的战斗力统一提升。这个过程通过更新士兵数量统计数组和总战斗力来高效完成，最后输出更新后的总战斗力，并为下一次训练找到新的最低战斗力值。
时间复杂度：O(n + m·MAX_POWER)，其中 MAX_POWER 为战斗力的最大值。
C++：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> powerCounts(200005, 0);
long long totalPower = 0;
int minPower = 200005;
for (int i = 0; i < n; i++) {
int power;
cin >> power;
powerCounts[power]++;
totalPower += power;
if (power < minPower) {
minPower = power;
}
}
for (int i = 0; i < m; i++) {
int b;
cin >> b;
while (minPower < powerCounts.size() && powerCounts[minPower] == 0) {
minPower++;
}
if (minPower >= powerCounts.size()) {
cout << totalPower;
if (i < m - 1) cout << " ";
continue;
}
int numSoldiers = powerCounts[minPower];
int newPower = minPower + b;
if (newPower < powerCounts.size()) {
powerCounts[newPower] += numSoldiers;
}
powerCounts[minPower] = 0;
totalPower += (long long)numSoldiers * b;
if (newPower < minPower) {
minPower = newPower;
}
cout << totalPower;
if (i < m - 1) cout << " ";
}
cout << endl;
return 0;
}
Java：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] powerCounts = new int[200005];
long totalPower = 0L;
int minPower = 200005;
for (int i = 0; i < n; i++) {
int power = sc.nextInt();
powerCounts[power]++;
totalPower += power;
if (power < minPower) {
minPower = power;
}
}
for (int i = 0; i < m; i++) {
int b = sc.nextInt();
while (minPower < powerCounts.length && powerCounts[minPower] == 0) {
minPower++;
}
if (minPower >= powerCounts.length) {
System.out.print(totalPower);
if (i < m - 1) System.out.print(" ");
continue;
}
int numSoldiers = powerCounts[minPower];
int newPower = minPower + b;
if (newPower < powerCounts.length) {
powerCounts[newPower] += numSoldiers;
}
powerCounts[minPower] = 0;
totalPower += (long) numSoldiers * b;
if (newPower < minPower) {
minPower = newPower;
}
System.out.print(totalPower);
if (i < m - 1) System.out.print(" ");
}
System.out.println();
sc.close();
}
}
Python：
def main():
n, m = map(int, input().split())
power_counts = [0] * 200005
total_power = 0
min_power = 200005
powers = list(map(int, input().split()))
for power in powers:
power_counts[power] += 1
total_power += power
if power < min_power:
min_power = power
b_values = list(map(int, input().split()))
results = []
for b in b_values:
while min_power < len(power_counts) and power_counts[min_power] == 0:
min_power += 1
if min_power >= len(power_counts):
results.append(str(total_power))
continue
num_soldiers = power_counts[min_power]
new_power = min_power + b
if new_power < len(power_counts):
power_counts[new_power] += num_soldiers
power_counts[min_power] = 0
total_power += num_soldiers * b
if new_power < min_power:
min_power = new_power
results.append(str(total_power))
print(' '.join(results))
if __name__ == "__main__":
main()
第二题：修改数字
有一串无序的正整数，现在允许你修改其中的一个，使得修改之后得到一个长度最长的单调递增子序列。
例如：4 1 2 2 1 4 3，你可以将第 4 个数字"2"改为"3"（也可以将第 5 个数字"1"改为"3"），这样可以得到长度为 4 的单调递增子序列 1 2 3 4。当然改变的方式并不唯一，因此我们只需要计算长度即可。
请你计算一个序列修改其中某一个数字之后可以得到的最大单调递增子序列的长度。
在本题目中，我们定义在单调递增子序列中后一个数字都要严格大于前一个数字。
输入描述
第 1 行一个正整数 n，表示输入序列中数字个数。(1 ≤ n ≤ 5000)
第 2 行 n 个正整数，两个正整数之间用空格隔开(正整数 ≤ 10⁹)。
输出描述
输出修改输入序列中某一个数字之后可以得到的最大单调递增子序列的长度。
样例输入
7
4 1 2 2 1 4 3
样例输出
4
参考题解
解题思路：
主要考虑两种情况来获得最长的单调递增子序列：
- 不修改任何数字或修改一个不属于最长子序列的数字：首先，计算出原数组中每个位置结尾的最长递增子序列的长度。这其中的最大值，再加一（因为我们可以修改一个数来延长这个最长的序列），就成为一个候选答案。
- 修改某个数字以连接两个子序列：分别计算从左到右以每个位置 i 结尾的最长递增子序列长度（lisLengths），和从右到左以每个位置 i 开始的最长递增子序列长度（ldsLengths）。通过遍历所有可能的位置组合 j 和 k（其中 j 在 k 左边），算法尝试将以 j 结尾的递增子序列和以 k 开始的递增子序列连接起来。这代表了修改 j 和 k 之间的一个数，从而形成一个更长的序列。这其中能得到的最大连接长度是另一个候选答案。
最终，输出这两个候选答案中较大的一个，即为问题的解。
时间复杂度：O(n²)
C++：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int count;
cin >> count;
vector<int> sequence(count);
for (int i = 0; i < count; i++) {
cin >> sequence[i];
}
if (count == 0) {
cout << 0 << endl;
return 0;
}
// 计算从左到右的最长递增子序列
vector<int> lisLengths(count);
int overallMaxLis = 0;
for (int i = 0; i < count; i++) {
lisLengths[i] = 1;
for (int j = 0; j < i; j++) {
if (sequence[j] < sequence[i]) {
lisLengths[i] = max(lisLengths[i], lisLengths[j] + 1);
}
}
overallMaxLis = max(overallMaxLis, lisLengths[i]);
}
// 计算从右到左的最长递增子序列
vector<int> ldsLengths(count);
for (int i = count - 1; i >= 0; i--) {
ldsLengths[i] = 1;
for (int j = count - 1; j > i; j--) {
if (sequence[j] > sequence[i]) {
ldsLengths[i] = max(ldsLengths[i], ldsLengths[j] + 1);
}
}
}
// 尝试连接两个子序列
int maxPossibleLength = 0;
for (int j = 0; j < count; j++) {
for (int k = j + 1; k < count; k++) {
if (sequence[j] < sequence[k]) {
maxPossibleLength = max(maxPossibleLength, lisLengths[j] + ldsLengths[k]);
}
}
}
int resultWithOneChange = min(count, overallMaxLis + 1);
cout << max(maxPossibleLength, resultWithOneChange) << endl;
return 0;
}
Java：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
int[] sequence = new int[count];
for (int i = 0; i < count; i++) {
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
上海得物信息集团有限公司公司福利 1170人发布
查看12道真题和解析