2026-03-15 某电商厂暑期笔试复盘
题目一：主播排序
题目大意
给定 N 个直播片段，第 i 个片段包含：
uid：主播编号A：指标 A，越大越好B：指标 B，越大越好T：时间，越早越好index：输入顺序，越早越好
排序规则依次比较：A 降序 → B 降序 → T 升序 → index 升序。
要求：
- 每个主播只保留其最优的一个片段；
- 用这些最优片段对主播排名；
- 有 Q 次询问，每次给一个片段编号 x：若 x 是该主播的最优片段，输出该主播的排名；否则输出 0。
思路分析
分组取最优，再用代表元素排序。
第一步遍历所有片段，对每个 uid 维护当前最优片段，比较规则就是题给的排序规则。
第二步把这些最优片段拿出来，按同一套规则排序，得到主播排名。
第三步处理询问：先判 x 是不是它所属主播的最优片段（直接与 best[uid] 记的编号比），不是就输出 0；是就输出这个主播的排名。
实现上有个小技巧：把 T、index 取负后塞进元组，四个维度就都统一成”越大越好”，直接按元组降序比较即可，不用手写比较函数，而且”选代表”和”排主播”两步可以复用同一套比较。因为 index 唯一，任意两个片段的键都不会相等，排名不存在并列。
复杂度 。
代码
import sys
def main():
data = sys.stdin.buffer.read().split()
p = 0
n = int(data[p]); p += 1
keys = [None] * (n + 1) # 片段编号 -> 排序键
uid_of = [0] * (n + 1) # 片段编号 -> 主播编号
best = {} # 主播编号 -> (排序键, 片段编号)
for seg in range(1, n + 1):
uid = int(data[p]); A = int(data[p + 1])
B = int(data[p + 2]); T = int(data[p + 3])
p += 4
# A 大、B 大、T 小、index 小 -> 全部转成"越大越好"
key = (A, B, -T, -seg)
keys[seg] = key
uid_of[seg] = uid
if uid not in best or key > best[uid][0]:
best[uid] = (key, seg)
# 第二步：用每个主播的最优片段排名
order = sorted(best.values(), key=lambda kv: kv[0], reverse=True)
rank = {}
for r, (_, seg) in enumerate(order, start=1):
rank[uid_of[seg]] = r
# 第三步：回答询问
q = int(data[p]); p += 1
out = []
for _ in range(q):
x = int(data[p]); p += 1
uid = uid_of[x]
if best[uid][1] != x:
out.append("0")
else:
out.append(str(rank[uid]))
sys.stdout.write("\n".join(out))
main()题目二：电动车充电最小费用
题目大意
一辆电动车要行驶总距离 L，电池容量 C（满电最多跑 C 公里），每行驶 1 公里消耗 1 单位电量。
路上有若干充电站，第 i 个位于位置 ，电价为每单位 。可以在任意站点买电，但电量不能超过 C。
求从起点到终点的最小花费；无法到达输出 -1。
题面没写出发时的电量，下面代码按”起点当作价格 0 的站点”处理，等价于满电出发。若原题是空箱出发、起点不能加油，把起点从站点列表里去掉、fuel 从 0 开始，其余逻辑不变。
思路分析
贪心。站在站点 i 往前看 C 公里：
- 如果范围内存在价格更低的站 j：只买到刚好能到 j 的电，到 j 时电量正好为 0。因为 j 的电更便宜，在 i 多买是亏的。
- 如果范围内没有更便宜的站：在 i 加满。因为接下来 C 公里内都比 i 贵，能囤就囤。
这里容易写错的一个点：要找的是范围内第一个更便宜的站，不是范围内最便宜的站 —— 因为一旦开到第一个更便宜的站，决策就在那里重新开始，后面的价格由那时的判断接管。
无解判断也简单：把起点、终点和所有站点按位置排序，任意相邻两点的距离超过 C，就有一段跑不过去，输出 -1。
单次决策要向前扫描可达范围内的站点，整体 。
代码
import sys
def main():
data = sys.stdin.buffer.read().split()
p = 0
L = int(data[p]); C = int(data[p + 1]); n = int(data[p + 2]); p += 3
st = []
for _ in range(n):
x = int(data[p]); pr = int(data[p + 1]); p += 2
st.append((x, pr))
st.sort()
pos = [0] + [x for x, _ in st] + [L]
price = [0] + [pr for _, pr in st] + [0] # 起点按价格 0（满电出发），终点只是占位
# 无解：任意相邻两点间距超过续航
for i in range(1, len(pos)):
if pos[i] - pos[i - 1] > C:
print(-1)
return
fuel = 0
cost = 0
for i in range(len(pos) - 1):
# 找可达范围内第一个比当前站便宜的站
j = i + 1
while j < len(pos) and pos[j] - pos[i] <= C and price[j] >= price[i]:
j += 1
if j < len(pos) and pos[j] - pos[i] <= C:
target = pos[j] - pos[i] # 买到刚好到 j
else:
target = C # 没有更便宜的，加满
if fuel < target:
cost += (target - fuel) * price[i]
fuel = target
fuel -= pos[i + 1] - pos[i] # 开到下一站
print(cost)
main()题目三：删除子串到达目标坐标
题目大意
给定长度为 N 的字符串 S，字符取自 U、D、L、R，分别表示二维平面上的上下左右移动。从 (0,0) 出发，按字符串依次移动。
允许执行一次操作：删除一个连续子串（也可以不删，也可以删除整个字符串）。
给定目标坐标 ，判断能否通过这样的删除使终点落在目标上。下面代码按”求最短删除长度，无解输出 -1”写；若原题只问可行性，把返回值当 bool 用即可。
思路分析
我的思路
考场上的做法是：先算出所有前缀和，用”目标坐标减总位移”得到要找的子串位移；然后扫前缀和，用字典记每个坐标最后出现的下标，查”当前坐标减 target”是否在字典里，命中就更新最短长度。
关于顺序，我当时是先存当前点、再查 当前点 - target。这没有问题：只有当 target 是 时才会匹配到自己，而那种情况答案本来就是 0。
推荐解法
设整串位移为 ，目标为 ，被删子串位移为 。删除后剩下部分的位移就是 ，要求它等于 ：
于是问题变成：是否存在一个连续子串，其位移恰好是 ；要最短删除长度，就取满足条件的子串里最短的那个。
用前缀和做： 表示前 i 个字符的位移，子串 的位移为 。条件是
所以扫到 i 时，只要在哈希表里查坐标 出现过没有；为了长度最短，表里存的应该是该坐标最后一次出现的下标。查完再把 写回表里。
两个边界：若 ，不删就已经到目标，答案是 0；若始终没命中，输出 -1。
整题 。我那份还原版和这个推荐版的差别只有两处： 的方向写成了 ，以及查表、存表的先后顺序。具体是哪一处让考场代码只过了部分数据，没有留下原始代码，这里不下结论。
代码
我的版本
按上面的思路还原，保留”方向用目标减总位移”和”先存再查”两个特征：
def shortest_delete(S, tx, ty):
n = len(S)
dx = {'U': 0, 'D': 0, 'L': -1, 'R': 1}
dy = {'U': 1, 'D': -1, 'L': 0, 'R': 0}
pre = [(0, 0)] * (n + 1)
for i, ch in enumerate(S):
pre[i + 1] = (pre[i][0] + dx[ch], pre[i][1] + dy[ch])
total = pre[n]
# 我当时写的方向：目标减总位移
need = (tx - total[0], ty - total[1])
last = {} # 坐标 -> 最后一次出现的下标
best = n + 1
for i in range(n + 1):
cur = pre[i]
last[cur] = i # 先存
look = (cur[0] - need[0], cur[1] - need[1])
if look in last: # 再查
best = min(best, i - last[look])
return best if best <= n else -1推荐版本
def shortest_delete(S, tx, ty):
n = len(S)
dx = {'U': 0, 'D': 0, 'L': -1, 'R': 1}
dy = {'U': 1, 'D': -1, 'L': 0, 'R': 0}
pre = [(0, 0)] * (n + 1)
for i, ch in enumerate(S):
pre[i + 1] = (pre[i][0] + dx[ch], pre[i][1] + dy[ch])
total = pre[n]
if total == (tx, ty):
return 0
need = (total[0] - tx, total[1] - ty) # 被删子串应有的位移 S - T
ans = n + 1
last = {} # 坐标 -> 最后一次出现的下标
for i in range(n + 1):
cur = pre[i]
want = (cur[0] - need[0], cur[1] - need[1])
if want in last: # 先查，保证 l < i
ans = min(ans, i - last[want])
last[cur] = i # 再存
return ans if ans <= n else -1题目四：资源包容量最小化
题目大意
给定两个长度为 N 的数组：
A[i]：第 i 个时段的峰值请求B[i]：第 i 个时段的原有容量
系统最多可以使用 M 个资源包。每个资源包的容量都是 x，持续 W 个时段；如果在第 i 个时段开启，则覆盖区间 ，超出序列长度也没关系。
要求所有时段满足 B[i] + 覆盖到该时段的资源包容量之和 A[i]。
求最小的资源包容量 x，以及在 x 最小时使用的资源包数量；无解输出 -1。
思路分析
单调性很明显：x 越大越容易满足，x 可行则任何更大的 x 也可行。所以二分 x，配一个线性判定 check(x)。
判定过程从左到右扫：维护当前生效的总贡献 cur 和已用包数 used。若 B[i] + cur < A[i]，缺口是 need = A[i] - B[i] - cur，一个包能补 x，就需要新开 个。新开的包覆盖 。
包的开启位置取 本身（能给当前缺口补量的最晚位置就是 i），越往后扫越该在最晚位置开，这样覆盖的时段不会浪费。
我的思路
二分框架我认出来了，判断函数按最直白的方式实现：开一个长度 N 的数组 add 记每个时段已生效的贡献，需要新开 k 个包时，就把 加到 的每一个位置上。写起来最直观，代价是每次判定 ，总复杂度 。
推荐解法
同样是二分，把贡献从”逐位加”换成差分数组维护：
- 新开包时，
cur当场加上 （本时段立刻生效）； - 只在位置
i + W记一笔 ，表示这批包到时失效；i + W越界就不记（题目说过界不影响）。
这样每次判定只扫一遍，，总复杂度 。
几个容易卡住的细节：
- 新开包后
cur必须立刻加上 gain，否则下个时段仍用旧的cur判断，会重复开包； - 向上取整写
(need + x - 1) // x； - 若所有
A[i] <= B[i]，答案是 0 个包、容量 0；否则二分下界从 1 开始； - 题目还要求输出 x 最小时的包数，所以
check直接返回used，超过 M 时返回None。
代码
两版共用下面这个主函数：
def solve():
hi = max((a - b for a, b in zip(A, B)), default=0)
if hi <= 0:
return 0, 0 # 本来就不用资源包
lo, ans, best_used = 1, None, None
while lo <= hi:
mid = (lo + hi) // 2
used = check(mid)
if used is not None:
ans, best_used = mid, used
hi = mid - 1 # 可行，试着更小
else:
lo = mid + 1 # 不可行，必须更大
return (ans, best_used) if ans is not None else -1我的版本
def check(x):
n = len(A)
add = [0] * n # 每个时段已生效的资源包贡献
used = 0
for i in range(n):
if B[i] + add[i] < A[i]:
need = A[i] - B[i] - add[i]
k = (need + x - 1) // x
used += k
if used > M:
return None
for t in range(i, min(n, i + W)): # 逐个时段加贡献，O(W)
add[t] += k * x
return used推荐版本
def check(x):
n = len(A)
diff = [0] * (n + 1) # 差分：在 i 处生效，在 i+W 处失效
cur = 0 # 当前生效的总贡献
used = 0
for i in range(n):
cur += diff[i]
if B[i] + cur < A[i]:
need = A[i] - B[i] - cur
k = (need + x - 1) // x
used += k
if used > M:
return None
gain = k * x
cur += gain # 本时段立刻生效
if i + W < n:
diff[i + W] -= gain # 到 i+W 失效
return used