写在前面

本次给大家带来2026年9月19日滴滴笔试题的3道题，本场机考题目可在咱们平台上在线刷题。

大厂笔试AI Coding练习:CodeFun2000.com/aicoder-gym

第1题-选择题

一、单选题

1、夜班质检要从一批尚未排序的测点读数里找出中位数，准备使用快速选择。平均时间复杂度是（ ）。{{ select(1) }}

2、园区闸机心跳走 UDP。UDP 协议提供的基本服务不包括（ ）。{{ select(2) }}

• 用端口号区分应用进程
• 发送前不必先建立连接
• 可靠交付和流量控制
• 用校验和做差错检测

3、单核质检台有 5 份工单要调度。若采用非抢占式短作业优先 (SJF)，这 5 份工单的执行顺序是：（ ）

{{ select(3) }}

• J3→J5→J4→J2→J1
• J1→J3→J5→J4→J2
• J1→J5→J3→J4→J2
• J2→J5→J4→J3→J1

4、门禁计数器类如下。下列程序的运行结果是（ ）

classSlot{staticint cnt;public:    Slot(){cnt++;}voiddump(){cout<<cnt;}voiddump(int x){cout<<cnt+x;}};int Slot::cnt=0;intmain(){    Slot p,q;    p.dump(3);    q.dump();return0;}

{{ select(4) }}

5、实验室仪器预约要互斥占用。解决死锁问题的几个方法中，可以使系统获得较好的资源利用率和系统吞吐量的方法的是：（ ）{{ select(5) }}

• 把全部仪器一次发给同一实验再运行
• 随机杀掉占用最久的进程
• 忽略互斥直接并发写设备
• 避免死锁

第2题-主题积压清零

题目内容

接入层挂着  条消息主题。第  条主题当前积压  条待处理记录，必须把每条主题的积压都清到  及以下，下游才允许继续接单。

调度器每一轮只能指定一条主题做主消费，这一轮的效果是：

1. 被指定的那条主题清掉  条积压。
2. 其余主题各清掉  条积压。保证 。

请计算最少需要多少轮，才能让全部主题的积压都不高于 。

题解

解题思路

每一轮相当于：所有主题积压减 ，被指定主消费的那条再多减 。设一共做  轮，第  条主题做主消费  轮，则 ，且

1.  越大越容易清完，具有单调性，可以二分 。
2. 下界：就算每轮都点积压最大的那条，也要  轮。上界：完全不做主消费、只靠顺带消费， 轮一定够。
3. 判定：顺带消费已经贡献 。若 ，这条不必再做主消费；否则还要做主消费  轮。所有  之和不超过  即可。
4.  到 ，乘积必须用  位。常见假解：每轮贪心点当前积压最大（局部最优不一定最少）、int 溢出、下界只取  却忘了上取整。

复杂度分析

• 时间复杂度：，，每次判定扫一遍主题。
• 空间复杂度：。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

defenough(times, heat, center, ambient):# times 轮是否够把所有积压清到不超过 0    extra = center - ambient    need = 0    cooled = ambient * timesfor w in heat:        rest = w - cooledif rest > 0:# 向上取整：还要做主消费多少轮            need += (rest + extra - 1) // extraif need > times:returnFalsereturnTruedefmin_starts(heat, center, ambient):    lo = 0    hi = 0for w in heat:        need_center = (w + center - 1) // centerif need_center > lo:            lo = need_center        need_amb = (w + ambient - 1) // ambientif need_amb > hi:            hi = need_ambwhile lo < hi:        mid = (lo + hi) // 2if enough(mid, heat, center, ambient):            hi = midelse:            lo = mid + 1return lodefmain():    m = int(input())    p, q = map(int, input().split())    w = list(map(int, input().split()))    print(min_starts(w, p, q))if __name__ == "__main__":    main()

第3题-时钟档位校准

题目内容

边缘推理集群里有  台节点，第  台当前的时钟偏移是 。运维每次只能挑一台节点，把它的偏移加上  或者减去 。这类微调可以重复任意多次。

现在有  项校准任务。第  项给出目标档 ，要求把所有节点的偏移都收进闭区间 。不同任务彼此独立：做完一项后偏移会恢复成一开始的 ，再处理下一项。

请对每项任务求出最少微调次数。

题解

时钟档位校准

一句话总结：每次微调改变 ，把  收进  的代价是 ，排序加前缀和后对每个  算出绝对值之和再扣掉奇偶差。

算法标签：排序、前缀和、二分、数学

算法难度：

解题思路

每次只能给某个偏移加  或减 ，所以奇偶不变。目标区间  里既有奇数也有偶数：

1. 与  同奇偶的数只能落到 ，代价是 。
2. 与  不同奇偶的数落到更近的  或 ，代价是 。
3. 因此总答案等于 。它又可以写成，其中  是与  不同奇偶的个数。
4.  把数组排序后用前缀和： 左边贡献 ，右边贡献 。 只取决于  的奇偶，预处理奇数个数即可。
5. 常见假解：直接输出 （奇偶个数  时会偏大）；用 int 累加（最大约 ）；对每个任务扫一遍数组（ 到  会超时）。

复杂度分析

• 时间复杂度：。排序一次，每个目标档二分两次。
• 空间复杂度：。存偏移、前缀和与答案

代码实现

python代码(C++和JAVA代码见在线OJ网址)

import bisectdefmin_ops(values, targets):# 排序后用前缀和，每次任务 O(log m) 算 sum |v-g|    arr = sorted(values)    m = len(arr)    pref = [0] * (m + 1)for i in range(m):        pref[i + 1] = pref[i] + arr[i]# 奇偶个数固定，用来把 sum |v-g| 改成 sum floor(|v-g|/2)    odd = 0for x in values:if x & 1:            odd += 1    even = m - odd    ans = []for g in targets:# 小于 g、大于 g 的两段分别贡献绝对值        lt = bisect.bisect_left(arr, g)        gt = bisect.bisect_right(arr, g)        sum_lt = pref[lt]        sum_gt = pref[m] - pref[gt]        cnt_gt = m - gt        sabs = g * lt - sum_lt + sum_gt - g * cnt_gt# 与 g 不同奇偶的数，floor 会各丢掉 1        diff = even if (g & 1) else odd        ans.append((sabs - diff) // 2)return ansdefmain():# 先读节点台数和偏移，再读任务条数与每个目标档    m = int(input())    values = list(map(int, input().split()))    k = int(input())    targets = []for _ in range(k):        targets.append(int(input()))    ans = min_ops(values[:m], targets)# 每项任务单独一行for x in ans:        print(x)if __name__ == "__main__":    main()