今天练习的是顺丰最新机考笔试题2题。

各大厂真题都整理了近两年的机考题，题库里面有详细思路和答案~

肥猫学长也提供机考辅导助攻（100%通过率）和面试辅导欢迎咨询。

微信号：jackwwang8

目前已经整理的题库有如下：如果有需要可以加我微信获取哦～

顺丰-27届秋招题目8.23

第1题 告警级别准入门槛

题目描述

运维侧汇总评估得到条告警记录。第条记录有两个整型字段：级别与占用额度。值班同学要选定一个非负整数门槛，只处理级别不低于该门槛的告警，且这些告警的额度之和不得超过预算。

对门槛，纳入集合为所有满足的记录，其额度总和记为：

若没有满足条件的记录，则。当且仅当时，门槛合法。请在所有合法门槛中，求最小的非负整数。

取大于所有级别时，纳入集合为空，因此合法门槛一定存在。若已合法，答案就是。

输入描述

数据范围：

输出描述

输出一个整数，表示最小合法门槛。

样例

输入：

3 64 27 51 3

输出：

5

说明：当时，纳入级别和，额度和为；当时，只纳入级别，额度为，因此最小合法门槛为。

解题思路

门槛增大时，满足的记录只会减少，因此单调不增。这意味着“门槛是否合法”具有明显的分界点，可以直接二分最小合法值。

为了快速计算任意门槛对应的额度和，先将所有记录按照级别升序排列，并建立额度前缀和。对于一个候选门槛，使用 bisect_left 找到第一条级别不小于的记录。该位置之前的记录不会被纳入，故：

二分区间取。右端点一定合法，因为它比所有告警级别都大，此时。若中点合法，就继续向左寻找；否则舍弃中点及其左侧范围。

这种写法不需要单独合并相同级别。排序后，二分查找会自然跳到该级别所有记录之前，仍能正确计算总额度。

复杂度分析

更加详细解题思路和 CPP、Java 代码加我微信获取：jackwwang8

from bisect import bisect_left
import sys
def minimum_threshold(records, budget):
    records.sort(key=lambda item: item[0])
    levels = [level for level, _ in records]
    prefix_cost = [0]
    for _, cost in records:
        prefix_cost.append(prefix_cost[-1] + cost)
    total_cost = prefix_cost[-1]
    def included_cost(threshold):
        first_included = bisect_left(levels, threshold)
        return total_cost - prefix_cost[first_included]
    left = 0
    right = levels[-1] + 1
    while left < right:
        middle = (left + right) // 2
        if included_cost(middle) <= budget:
            right = middle
        else:
            left = middle + 1
    return left
def main():
    input_data = sys.stdin.readline
    record_count, budget = map(int, input_data().split())
    records = [
        tuple(map(int, input_data().split()))
        for _ in range(record_count)
    ]
    print(minimum_threshold(records, budget))
if __name__ == "__main__":
    main()

第2题 最小缺货总件数

题目描述

共有个时刻，编号到。给定三个长度为的整数数组。

在时刻，依次发生：

每次出库时，可以任意选择取出哪些有效物品。请合理安排，使所有时刻缺货件数之和最小，并输出该最小值。

输入描述

数据范围：

输出描述

输出一个整数，表示最小缺货总件数。

样例

输入：

33 4 32 1 11 3 1

输出：

2

说明：时刻入库件并取出件；时刻有效库存共件，但需求为，缺货件；时刻的新入库物品已经失效，此时再缺货件，因此总缺货为。

解题思路

每次出库都应优先使用最早过期的库存。假设当前有两批库存，过期时刻分别为。如果先使用过期较晚的那一批，较早过期的库存可能在后续需求到来前失效；改为先用过期时刻的库存，不会减少时刻那批库存未来的可用机会。因此交换后结果不会变差，最早过期优先是最优策略。

实现时，用小根堆保存当前存在的过期时刻，再用字典记录每个过期时刻对应的库存总量。这样，同一过期时刻的多批货物会自动合并，不需要在堆中保存多份相同节点。

对每个时刻依次执行：

数组中的数量可能达到，累计缺货可能超过 32 位整数范围；Python 整数可以直接保存该结果。

复杂度分析

更加详细解题思路和 CPP、Java 代码加我微信获取：jackwwang8

import heapq
import sys
def minimum_shortage(expire_input, arrivals, demands):
    active_deadlines = []
    stock_by_deadline = {}
    total_shortage = 0
    for day, (expire_value, arrival, demand) in enumerate(
        zip(expire_input, arrivals, demands),
        start=1,
    ):
        while active_deadlines and active_deadlines[0] < day:
            expired = heapq.heappop(active_deadlines)
            stock_by_deadline.pop(expired, None)
        deadline = expire_value - 1
        if arrival > 0 and deadline >= day:
            if deadline not in stock_by_deadline:
                stock_by_deadline[deadline] = 0
                heapq.heappush(active_deadlines, deadline)
            stock_by_deadline[deadline] += arrival
        remaining_demand = demand
        while remaining_demand > 0 and active_deadlines:
            nearest_deadline = active_deadlines[0]
            available = stock_by_deadline[nearest_deadline]
            used = min(remaining_demand, available)
            remaining_demand -= used
            available -= used
            if available == 0:
                heapq.heappop(active_deadlines)
                del stock_by_deadline[nearest_deadline]
            else:
                stock_by_deadline[nearest_deadline] = available
        total_shortage += remaining_demand
    return total_shortage
def main():
    input_data = sys.stdin.readline
    time_count = int(input_data())
    expire_input = list(map(int, input_data().split()))
    arrivals = list(map(int, input_data().split()))
    demands = list(map(int, input_data().split()))
    print(minimum_shortage(expire_input, arrivals, demands))
if __name__ == "__main__":
    main()