大家好，我是吴师兄，关注我，每周更新大厂最新笔试题解析。
题目描述
8月份发布会一结束，米小兔就在公司领到了一台最新发布的Xiaomi MIX Fold 3手机，这是一款小米旗舰折叠屏手机，并搭载了全新升级架构的MIU114系统。其先进的应用引擎不仅让系统更流畅，应用体验也大幅提升。
在一个优化项中，为了尽可能提升用户白天使用手机的体验和续航，某些已经在系统中注册过的任务会被设置为空闲任务，仅在手机空闲时运行 (比如数据备份或AI相册整理)。现在系统中注册了若干组空闲任务，每个任务有各自的耗电量以及允许任务运行的最低初始电量，我们需要计算手机能够串行完成全部任务的最低初始电量。
注意点1: 所有电量以mAh(毫安时)计，Xiaomi MIX Fold 3的大电池容量是4800mAh。
注意点2:本题目假设手机在运行空闲任务期间，不处于充电状态，也没有额外耗电行为。
注意点3:智能应用引擎会以最合适的顺序串行运行任务。
输入描述
一个描述了所有任务的长字符串。任务与任务之间用逗号隔开，每组任务由耗电量及最低初始电量组成，用冒号隔开。
输出描述
一个数字，代表依次完成全部任务的最低初始电量，如果最低初始电量超过手机电池容量，则返回-1。
示例
输入
代码语言：javascript复制1:10,2:12,3:10
输出
代码语言：javascript复制13
说明
在样例中，手机至少需要有13mAh的初始电量，在运行任务2后剩余电量11mAh、运行任务1后剩余电量10mAh、运行任务3后剩余7mAh。
时空限制
时间限制： 1000MS
内存限制： 65536KB
解题思路
题干花里胡哨，题意令人费解。
用比较通俗的语言来讲就是：需要串行地运行N个任务，每个任务都包含两个数据，运行完毕所消耗电量和开始运行时至少需要的电量。求最少需要多少电量？
显然这个问题可以通过对原数组贪心地进行排序来解决，从电量0开始考虑。那么排序的依据如何选取呢？
为了方便使用，对于第i个任务，我们将其消耗电量和运行时至少需要的电量记为consumed_electricity_i和least_electricity_i。排序依据如下：
- 把
least_electricity_i较小的任务排在数组前面，优先被考虑。 - 在
least_electricity_i相等时，我们则选择consumed_electricity_i较大的任务排在数组前面。
lst = input().split(",")
lst = [tuple(map(int, s.split(":"))) for s in lst]
lst.sort(key = lambda x: (x[1], -x[0]))
然后初始化ans为lst[0]中的较大值，为执行任务0前，至少需要的电量。接着遍历lst中，除了任务0之外的其他所有任务i。若
ans consumed_electricity >= least_electricity，即当前电量 任务i消耗电量大于任务i运行的最少电量，则应该更新当前电量 任务i消耗电量为执行任务i前，至少需要的电量ans consumed_electricity < least_electricity，直接更新ans为任务i运行所需的最少电量，即least_electricity
ans = max(lst[0])
for consumed_electricity, least_electricity in lst[1:]:
if ans consumed_electricity >= least_electricity:
ans = consumed_electricity
else:
ans = least_electricity
代码
代码语言：javascript复制# 题目：【贪心】小米2023秋招-手机流畅运行的秘密
# 作者：闭着眼睛学数理化
# 算法：贪心/排序
# 代码有看不懂的地方请直接在群上提问
# 根据","进行分割，得到n个任务的情况
lst = input().split(",")
# 对lst中的每个元素再次根据":"进行切割
lst = [tuple(map(int, s.split(":"))) for s in lst]
# 对lst贪心地进行排序
# 先根据least_electricity_i从小到大进行排序
# 再根据consumed_eletricity_i从大到小进行排序
lst.sort(key = lambda x: (x[1], -x[0]))
# 选择lst[0]中的较大值，作为ans的起始位置
# 即执行任务0前，至少需要的电量
ans = max(lst[0])
# 遍历lst中，除了任务0之外的所有任务
# 考虑执行任务i时的情况
for consumed_electricity, least_electricity in lst[1:]:
# 如果【当前电量 任务i消耗电量】大于【任务i运行的最少电量】
# 那么应该更新【当前电量 任务i消耗电量】为执行任务i前，至少需要的电量
if ans consumed_electricity >= least_electricity:
ans = consumed_electricity
# 否则，直接更新ans为任务i运行所需的最少电量，即least_electricity
else:
ans = least_electricity
# 输出最终结果，要注意电量的最大容量是4800
print(ans) if ans <= 4800 else print(-1)
时空复杂度
时间复杂度：O(NlogN)。排序所需的时间复杂度。
空间复杂度：O(1)。忽略排序使用的编译栈空间，仅需若干常数变量。
题目描述
小米手机生产过程中会经过严苛的测试环节，其中包括手机通讯功能中的射频校准。射频校准会打点数据上报到云端。其中包含两组数据:第一组数据中会包含此次校准的频道号(freq)信息；第二组会上传一批数据，包含一组频道号(freg)和其对应的损失值(loss)，其中这一组频道号(freg)不会重复，且是有序的。
现在需要根据第一组数据中的频道号(freg)，找到离第二组中频道号(freq)最近的那个freq对应的loss值，如果两边一样近，则取两边loss的平均。
注：输入为int，输出为double类型四舍五入保留1位小数
输入描述
包含两组数据:
第一组数据中会包含此次校准的频道号(freq)信息。
第二组会上传一批数据，包含一组频道号(freg)和其对应的损失值(loss)，其中这一组频道号(freg)不会重复，且是有序的。
输出描述
离频道号(freq)最近的freq对应的loss值，如果两边一样近，则取两边loss的平均。
示例
输入
代码语言：javascript复制2800
1950:10 2000:15 3000:9
输出
代码语言：javascript复制9.0
时空限制
时间限制： 1000MS
内存限制： 65536KB
解题思路
本题是非常直接的二分查找题目，直接对包含(freq, loss)的有序二元数组lst进行二分查找即可。
找到第一个大于等于target_freq的freq在lst中的的位置i，并且根据target_freq和lst[i][0]、lst[i 1][0]之间距离，输出结果。
代码
代码语言：javascript复制# 题目：【二分查找】小米2023秋招-小米手机通信校准
# 作者：闭着眼睛学数理化
# 算法：二分查找
# 代码有看不懂的地方请直接在群上提问
target_freq = int(input())
# 根据空格" "进行分割，得到n个二元元组(freq, loss)的情况
lst = input().split()
# 对lst中的每个元素再次根据":"进行切割
lst = [tuple(map(int, s.split(":"))) for s in lst]
n = len(lst)
# 构建左闭右开区间
left, right = 0, n
# 进行二分查找
while left < right:
mid = left (right - left) // 2
# mid对应的freq较大，right左移
if lst[mid][0] >= target_freq:
right = mid
# mid对应的freq较小，left右移
else:
left = mid 1
# 退出循环时，索引left = right对应的freq，
# 是大于等于target_freq的第一个freq
# 需要考虑left和left-1对用的freq和target_freq的差值
# 如果left为n，说明lst中的任意一个二元组的freq都小于target_freq
# 输出lst中freq最大的元素对应的loss，lst[-1][1]
ans = 0
if left == n:
ans = lst[-1][1]
# 如果left为0，说明lst中的任意一个二元组的freq都大于target_freq
# 输出lst中freq最小的元素对应的loss，lst[0][1]
elif left == 0:
ans = lst[0][1]
# 其他情况，考虑left和left-1对应的freq
else:
# 离lst[left][0]更近
if lst[left][0] - target_freq < target_freq - lst[left-1][0]:
ans = lst[left][1]
# 离lst[left-1][0]更近
elif lst[left][0] - target_freq > target_freq - lst[left-1][0]:
ans = lst[left-1][1]
# 一样近
else:
ans = (lst[left][1] lst[left-1][1]) / 2
# 保留一位小数后输出
print("{:.1f}".format(ans))
时空复杂度
时间复杂度：O(logN)。二分查找所需的时间复杂度。
空间复杂度：O(1)。仅需若干常数变量。
