小米笔试 小米笔试题 0312
笔试时间：2025年03月12 春招实习
历史笔试传送门：
第一题
题目：因为山就在那里
作为一个登山爱好者，Bob现在正计划向珠峰发起挑战，要问为什么的话，因为山就在那里！珠峰的气候变幻莫测，并不是每天都适合登山，但Bob通过东方神秘力量了解到接下来有n个特定日期可能会是适合登山的好日子。因此他在这n天一定要在珠峰大本营等待良机。然而，海拔5200米的珠峰大本营不是久居之地。根据医生的评估，Bob最多能够在此处生活的总天数为k天，否则出现生命危险的概率将大大增加。因此Bob需要注意在不适合登山的日子下撤回低海拔地区。下撤回低海拔地区和前往珠峰大本营的旅费不可小觑，Bob自身也讨厌频繁移动。因此请你告诉他，在不错过n个特定日期，同时在珠峰大本营生活不超过总共k天的前提下，最少需要多少次移动？注意，Bob一开始位于低海拔地区，最终也必须回到低海拔地区。一次移动指的是单程而非往返，即从低海拔地区前往珠峰大本营或从珠峰大本营下撤回低海拔地区分别是一次移动。
输入描述
第一行两个正整数n，k，表示可能适合登山的日子天数和Bob最多能在珠峰大本营生活的天数 ;
第二行n个正整数ai，表示第i个可能适合登山的日子是接下来的第ai天，保证递增。
输出描述
一行，输出一个正整数，表示最少的移动次数。
样例输入
5 8
2 3 5 6 10
样例输出
4
参考题解
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int tot = a.back() - a[0] + 1;
vector<int> df;
for (int i = 0; i < n - 1; ++i) {
int gap = a[i + 1] - a[i] - 1;
if (gap > 0) {
df.push_back(gap);
}
}
sort(df.begin(), df.end());
int cnt = 0;
while (true) {
if (tot <= k) break;
if (df.empty()) break;
tot -= df.back();
cnt += 2;
df.pop_back();
}
cout << cnt + 2 << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++){
a[i] = sc.nextInt();
}
// 初始段数 tot = a[n-1] - a[0] + 1
int tot = a[n-1] - a[0] + 1;
// 记录相邻元素间的 gap
List<Integer> df = new ArrayList<>();
for(int i = 0; i < n-1; i++){
int gap = a[i+1] - a[i] - 1;
if(gap > 0){
df.add(gap);
}
}
// gap 排序
Collections.sort(df);
int cnt = 0;
// 从最大的 gap 开始减少 tot，直到 tot <= k 或没剩 gap
while(true) {
if(tot <= k) break;
if(df.isEmpty()) break;
// 取最大的 gap
int g = df.remove(df.size() - 1);
tot -= g;
cnt += 2;
}
// 输出结果
System.out.println(cnt + 2);
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve():
import sys
data = sys.stdin.read().strip().split()
# 如果要行读取，也可以用 sys.stdin.readline
n = int(data[0])
k = int(data[1])
a = list(map(int, data[2:]))
# 初始段数
tot = a[-1] - a[0] + 1
# 收集相邻间的 gap
df = []
for i in range(n - 1):
gap = a[i+1] - a[i] - 1
if gap > 0:
df.append(gap)
# 排序 gap
df.sort()
cnt = 0
# 从最大的 gap 开始尝试减少 tot
while True:
if tot <= k:
break
if not df:
break
g = df.pop() # 取最大 gap
tot -= g
cnt += 2
print(cnt + 2)
# 如果在本地/在线评测使用标准输入输出，可改用:
# def solve():
# import sys
# input_data = sys.stdin
# n, k = map(int, next(input_data).split())
# a = list(map(int, next(input_data).split()))
#
# tot = a[-1] - a[0] + 1
# df = []
# for i in range(n-1):
# gap = a[i+1] - a[i] - 1
# if gap > 0:
# df.append(gap)
# df.sort()
# cnt = 0
#
# while True:
# if tot <= k:
# break
# if not df:
# break
# g = df.pop()
# tot -= g
# cnt += 2
#
# print(cnt + 2)
第二题
题目：采购汽车
小李负责公司的汽车采购业务。最近公司需要采购一批汽车，保证其可以载X人，承货Y立方米。小李调研了市场的n种汽车。对第i种汽车价值mi元，有ki种选配方案。默认的方案可以承载xi人，承货yi立方米。第j种选配方案需要金额变化为mij元，可以选配特殊的座椅或者支架使得载人和承货能力发生变化，载人变化值为xij载货变化值为yij。每辆车只能选择一种选配方案，或者选择默认方案。小李可以同时采购多种汽车的多种选配方案，只希望花费最少的金额满足要求。
输入描述
第一行包括三个正整数X,y,n，这三个数取值范围都在[1,200]中。
然后是n组数据: 其中第i组第一行包括四个整数mi, xi, yi, ki
接下来行每行包括3个整数mij,xij,yij
输出描述
输出一个整数，表示最少花费金额。
样例输入
10 20 2
100 2 6 1
20 1 1
80 5 1 1
10 -1 2
样例输出
390
购买原装第一款车3辆，第二款车的第一种选配1辆即可。
参考题解
分组完全背包问题，首先需要进行分组，并且每个组中只能选择一种类型进行购买。
C++：[此代码未进行大量数据的测试，仅供参考]
#include<bits/stdc++.h>
using namespace std;
int main() {
int X, Y, n;
cin >> X >> Y >> n;
vector<vector<vector<int>>> thing;
vector<vector<long long>> DP(X + 1, vector<long long>(Y + 1, 1e18));
DP[0][0] = 0;
for (int i = 0; i < n; ++i) {
int m, x, y, k;
cin >> m >> x >> y >> k;
vector<vector<int>> gp;
gp.push_back({m,x,y});
for (int j = 0; j < k; ++j) {
int cm, cx, cy;
cin >> cm >> cx >> cy;
gp.push_back({m + cm, x + cx, y + cy});
}
thing.push_back(gp);
}
for (int i = 0; i < thing.size(); ++i) {
for (int x = 0; x <= X; ++x) {
for (int y = 0; y <= Y; ++y) {
for (const auto& tmp : thing[i]) {
DP[x][y] = min(DP[x][y], DP[max(0, x - tmp[1])][max(0, y - tmp[2])] + tmp[0]);
}
}
}
}
cout << DP[X][Y] << endl;
return 0;
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve():
import sys
data = sys.stdin.read().strip().split()
idx = 0
X = int(data[idx]); idx += 1
Y = int(data[idx]); idx += 1
n = int(data[idx]); idx += 1
thing = []
for _ in range(n):
m = int(data[idx]); idx += 1
xx = int(data[idx]); idx += 1
yy = int(data[idx]); idx += 1
k = int(data[idx]); idx += 1
gp = []
gp.append((m, xx, yy))
for __ in range(k):
cm = int(data[idx]); idx += 1
cx = int(data[idx]); idx += 1
cy = int(data[idx]); idx += 1
gp.append((m + cm, xx + cx, yy + cy))
thing.append(gp)
INF = 10**15 # 或者更大
DP = [[INF]*(Y+1) for _ in range(X+1)]
DP[0][0] = 0
# 逐组更新
for gp in thing:
for x in range(X+1):
for y in range(Y+1):
# 逐个三元组尝试更新
for (cost, useX, useY) in gp:
px = max(0, x - useX)
py = max(0, y - useY)
if DP[px][py] + cost < DP[x][y]:
DP[x][y] = DP[px][py] + cost
print(DP[X][Y])
# 如果要做行读取可以写成：
#
# def solve():
# import sys
# input_data = sys.stdin
# X, Y, n = map(int, next(input_data).split())
#
# thing = []
# for _ in range(n):
# m, xx, yy, k = map(int, next(input_data).split())
# gp = []
# gp.append((m, xx, yy))
# for __ in range(k):
# cm, cx, cy = map(int, next(input_data).split())
# gp.append((m+cm, xx+cx, yy+cy))
# thing.append(gp)
#
# INF = 10**15
# DP = [[INF]*(Y+1) for _ in range(X+1)]
# DP[0][0] = 0
#
# for gp in thing:
# for x in range(X+1):
# for y in range(Y+1):
# for (cost, useX, useY) in gp:
# px = max(0, x-useX)
# py = max(0, y-useY)
# DP[x][y] = min(DP[x][y], DP[px][py] + cost)
#
# print(DP[X][Y])
#小米求职进展汇总##小米笔试##小米提前批笔试难吗##小米#2025打怪升级记录，大厂笔试合集
投递小米集团等公司10个岗位