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 唯一，任意两个片段的键都不会相等，排名不存在并列。

复杂度 $O(N \log N + Q)$ 。

代码

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 个位于位置 $x_i$ ，电价为每单位 $p_i$ 。可以在任意站点买电，但电量不能超过 C。

求从起点到终点的最小花费；无法到达输出 -1。

题面没写出发时的电量，下面代码按”起点当作价格 0 的站点”处理，等价于满电出发。若原题是空箱出发、起点不能加油，把起点从站点列表里去掉、fuel 从 0 开始，其余逻辑不变。

思路分析

贪心。站在站点 i 往前看 C 公里：

如果范围内存在价格更低的站 j：只买到刚好能到 j 的电，到 j 时电量正好为 0。因为 j 的电更便宜，在 i 多买是亏的。
如果范围内没有更便宜的站：在 i 加满。因为接下来 C 公里内都比 i 贵，能囤就囤。

这里容易写错的一个点：要找的是范围内第一个更便宜的站，不是范围内最便宜的站 —— 因为一旦开到第一个更便宜的站，决策就在那里重新开始，后面的价格由那时的判断接管。

无解判断也简单：把起点、终点和所有站点按位置排序，任意相邻两点的距离超过 C，就有一段跑不过去，输出 -1。

单次决策要向前扫描可达范围内的站点，整体 $O(n \cdot \text{可达站数})$ 。

代码

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) 出发，按字符串依次移动。

允许执行一次操作：删除一个连续子串（也可以不删，也可以删除整个字符串）。

给定目标坐标 $(tx, ty)$ ，判断能否通过这样的删除使终点落在目标上。下面代码按”求最短删除长度，无解输出 -1”写；若原题只问可行性，把返回值当 bool 用即可。

思路分析

我的思路

考场上的做法是：先算出所有前缀和，用”目标坐标减总位移”得到要找的子串位移；然后扫前缀和，用字典记每个坐标最后出现的下标，查”当前坐标减 target”是否在字典里，命中就更新最短长度。

关于顺序，我当时是先存当前点、再查 当前点 - target。这没有问题：只有当 target 是 $(0,0)$ 时才会匹配到自己，而那种情况答案本来就是 0。

代码

我的版本

按上面的思路还原，保留”方向用目标减总位移”和”先存再查”两个特征：

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

题目四：资源包容量最小化

题目大意

给定两个长度为 N 的数组：

A[i]：第 i 个时段的峰值请求
B[i]：第 i 个时段的原有容量

系统最多可以使用 M 个资源包。每个资源包的容量都是 x，持续 W 个时段；如果在第 i 个时段开启，则覆盖区间 $[i, i+W-1]$ ，超出序列长度也没关系。

要求所有时段满足 B[i] + 覆盖到该时段的资源包容量之和 $\ge$ 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，就需要新开 $\lceil need / x \rceil$ 个。新开的包覆盖 $[i, i+W-1]$ 。

包的开启位置取 $i$ 本身（能给当前缺口补量的最晚位置就是 i），越往后扫越该在最晚位置开，这样覆盖的时段不会浪费。

我的思路

二分框架我认出来了，判断函数按最直白的方式实现：开一个长度 N 的数组 add 记每个时段已生效的贡献，需要新开 k 个包时，就把 $k \cdot x$ 加到 $i \sim i+W-1$ 的每一个位置上。写起来最直观，代价是每次判定 $O(N \cdot W)$ ，总复杂度 $O(N \cdot W \cdot \log V)$ 。

代码

两版共用下面这个主函数：

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

2026-03-15 某电商厂暑期笔试复盘

2026-03-15 某电商厂暑期笔试复盘

题目一：主播排序

题目大意

思路分析

代码

题目二：电动车充电最小费用

题目大意

思路分析

代码

题目三：删除子串到达目标坐标

题目大意

思路分析

我的思路

推荐解法

代码

我的版本

推荐版本

题目四：资源包容量最小化

题目大意

思路分析

我的思路

推荐解法

代码

我的版本

推荐版本

Random Posts