✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

拼多多-2026.03.15

1. 小基 的直播榜单巡检

问题描述

小基 负责直播广场首页榜单的巡检工作。今天系统一共收到了 条候选直播内容，按录入顺序依次编号为 到 。

第 条内容属于主播 ，同时带有三项榜单指标：点赞数 、评论数 、发布时间 。其中， 越小表示发布时间越早。

为了避免同一位主播同时占据多个榜单位置，平台在正式出榜前会先做一次主播去重。对于同一主播的多条内容，只保留其中“最优”的那一条，其余内容会直接淘汰，不再参与后续排名。

两条内容谁更优，按下面的顺序比较：

1. 点赞数更多的更优。
2. 如果点赞数相同，评论数更多的更优。
3. 如果点赞数和评论数都相同，发布时间更早的更优。
4. 如果前三项仍然完全相同，原始编号更小的更优。

完成主播去重后，再把所有保留下来的内容按完全相同的规则排序，得到最终直播榜单。

现在有 次询问。每次给出一个原始编号 ，需要判断这条内容的最终结果：

1. 如果它在主播去重阶段已经被淘汰，输出 。
2. 如果它最终仍然留在榜单中，输出它的榜单排名，排名从 开始。

输入格式

第一行输入两个整数 ，分别表示候选直播内容数量和询问数量。

接下来 行，每行输入四个整数 ，表示第 条内容所属的主播编号、点赞数、评论数和发布时间。

接下来 行，每行输入一个整数 ，表示询问原始编号为 的那条内容。

输出格式

输出 行，每行一个整数。

如果对应内容已经在主播去重阶段被淘汰，输出 ；否则输出它在最终直播榜单中的排名。

样例输入

5 4
1 100 20 5
1 120 10 8
3 130 25 4
2 100 18 6
1 120 10 7
1
2
3
5

样例输出

0
0
1
2

数据范围

• 
• 
• 
• 

样例	解释说明
样例 1	编号 、、 都属于同一位主播。去重后只保留编号 ，因为它和编号 的点赞数、评论数相同，但发布时间更早。最终留下的三条内容是编号 、、，其中编号 的点赞数最高，所以排第 ；编号 排第 。因此查询编号 、 时输出 ，查询编号 、 时分别输出 和 。

题解

这题看起来像“查每条内容最后排第几”，真正的核心其实只有两步：

1. 先在每个主播内部选出唯一代表。
2. 再把所有代表拿出来做一次全局排名。

这两个阶段的排序规则完全一样，但顺序不能反。因为同一主播后面可能还会出现更优内容，前面那条即使暂时看起来不错，也可能在去重阶段直接出局。只有每个主播的代表都确定下来以后，最终榜单的排名才真正固定。

一、把比较规则写成统一的“优先级键”

对于一条内容 ，它的关键信息是 。

题目要求“点赞更多更优、评论更多更优、时间更早更优、编号更小更优”。
如果改成便于程序排序的形式，可以写成下面这个键：。

按这个键做字典序升序比较时，排在前面的那条内容就是更优内容。

这样做的好处是，主播去重和最终排名都能共用同一套比较逻辑，不容易写乱。

二、第一阶段：先做主播去重

扫描输入的 条内容。

用一个哈希表记录每位主播当前保留的是哪条内容。设 best[u] 表示主播 当前的代表编号。

当读到一条新内容时：

1. 如果这个主播之前还没有代表，直接把它记成代表。
2. 如果已经有代表，就用上面的比较规则判断新内容和旧代表谁更优。
3. 更优的那条留下来，另一条以后就不用再考虑了。

扫完整个输入后，每位主播都只剩下一条最优内容。这一步完全符合题意中的“主播去重”。

三、第二阶段：对所有代表求最终排名

把第一阶段保留下来的所有代表取出来，再按同样的规则排序。

排完以后：

1. 排在第 个的代表，最终排名就是 。
2. 排在第 个的代表，最终排名就是 。
3. 以此类推。

然后开一个数组或哈希表 rk[id] 记录“原始编号 的最终排名”。

如果某条内容是代表，就会在 rk 里留下一个正整数排名；如果它不是代表，rk 里没有它，查询时输出 即可。

四、为什么这样做一定正确

正确性分两部分看。

第一部分是主播去重。

对任意一位主播，第一阶段会把这个主播的所有内容两两比较，最后留下其中最优的一条。题目明确规定，最终只有这条内容可以进入候选榜单，所以第一阶段结束后的结果就是“去重后应当保留的集合”。

第二部分是最终排名。

题目又规定：去重完成后，对保留下来的所有内容继续按完全相同的规则排序。第二阶段做的正是这件事，所以排出来的位置就是最终榜单排名。

两步连起来，恰好与题意一一对应，因此答案正确。

五、实现细节

实现时有两个容易写错的点。

1. 编号 也是比较规则的一部分。前三项都相同时，编号更小的内容更优，这个 tie-break 不能漏。
2. 查询的是原始编号，不是主播编号。所以最终一定要把“代表编号 -> 排名”映射回原始编号。

六、复杂度分析

设不同主播的数量为 ，显然有 。

• 第一阶段扫描一遍输入，时间复杂度是 。
• 第二阶段对 条代表排序，时间复杂度是 。
• 回答 次询问，时间复杂度是 。

总时间复杂度为 。

因为 ，所以也可以写成 。

空间复杂度是 。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()


def better(x, y):
    # 返回 x 是否比 y 更优
    if x[1] != y[1]:
        return x[1] > y[1]
    if x[2] != y[2]:
        return x[2] > y[2]
    if x[3] != y[3]:
        return x[3] < y[3]
    return x[4] < y[4]


def key_of(x):
    # 排序时复用同一套优先级
    return (-x[1], -x[2], x[3], x[4])


n, q = map(int, input().split())
best = {}

for i in range(1, n + 1):
    u, a, b, t = map(int, input().split())
    cur = (u, a, b, t, i)

    # 每个主播只保留当前最优的那条内容
    old = best.get(u)
    if old is None or better(cur, old):
        best[u] = cur

# 取出所有主播代表，再按题目规则排最终榜单
lst = list(best.values())
lst.sort(key=key_of)

# 记录“原始编号 -> 最终排名”
rk = {}
for i, item in enumerate(lst, 1):
    rk[item[4]] = i

out = []
for _ in range(q):
    idx = int(input())
    out.append(str(rk.get(idx, 0)))

sys.stdout.write("\n".join(out))

• Cpp

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long u, a, b, t;
    int id;
};

bool better(const Node& x, const Node& y) {
    // 按题目给定规则判断 x 是否更优
    if (x.a != y.a) return x.a > y.a;
    if (x.b != y.b) return x.b > y.b;
    if (x.t != y.t) return x.t < y.t;
    return x.id < y.id;
}

bool cmp(const Node& x, const Node& y) {
    // 最终榜单排序同样使用这一套规则
    if (x.a != y.a) return x.a > y.a;
    if (x.b != y.b) return x.b > y.b;
    if (x.t != y.t) return x.t < y.t;
    return x.id < y.id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    unordered_map<long long, int> best;
    vector<Node> arr(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> arr[i].u >> arr[i].a >> arr[i].b >> arr[i].t;
        arr[i].id = i;

        auto it = best.find(arr[i].u);
        // 同一主播只维护一个当前代表
        if (it == best.end() || better(arr[i], arr[it->second])) {
            best[arr[i].u] = i;
        }
    }

    vector<Node> lst;
    lst.reserve(best.size());
    for (const auto& kv : best) {
        lst.push_back(arr[kv.second]);
    }

    // 所有代表统一排序，得到最终榜单
    sort(lst.begin(), lst.end(), cmp);

    vector<int> rk(n + 1, 0);
    for (int i = 0; i < (int)lst.size(); ++i) {
        rk[lst[i].id] = i + 1;
    }

    while (q--) {
        int id;
        cin >> id;
        cout << rk[id] << '\n';
    }

    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class Main {
    static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buf = new byte[1 << 16];
        private int len = 0, ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            long sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            long val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }

        int nextInt() throws IOException {
            return (int) nextLong();
        }
    }

    static class Node {
        long u, a, b, t;
        int id;

        Node(long u, long a, long b, long t, int id) {
            this.u = u;
            this.a = a;
            this.b = b;
            this.t = t;
            this.id = id;
        }
    }

    static boolean better(Node x, Node y) {
        // 按题意判断 x 是否比 y 更优
        if (x.a != y.a) return x.a > y.a;
        if (x.b != y.b) return x.b > y.b;
        if (x.t != y.t) return x.t < y.t;
        return x.id < y.id;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        int q = fs.nextInt();

        Node[] arr = new Node[n + 1];
        HashMap<Long, Integer> best = new HashMap<>();

        for (int i = 1; i <= n; i++) {
            long u = fs.nextLong();
            long a = fs.nextLong();
            long b = fs.nextLong();
            long t = fs.nextLong();
            arr[i] = new Node(u, a, b, t, i);

            Integer old = best.get(u);
            // 每个主播只保留当前最优代表
            if (old == null || better(arr[i], arr[old])) {
                best.put(u, i);
            }
        }

        List<Node> lst = new ArrayList<>();
        for (int id : best.values()) {
            lst.add(arr[id]);
        }

        // 按最终榜单规则排序所有代表
        Collections.sort(lst, new Comparator<Node>() {
            @Override
            public int compare(Node x, Node y) {
                if (x.a != y.a) return Long.compare(y.a, x.a);
                if (x.b != y.b) return Long.compare(y.b, x.b);
                if (x.t != y.t) return Long.compare(x.t, y.t);
                return Integer.compare(x.id, y.id);
            }
        });

        int[] rk = new int[n + 1];
        for (int i = 0; i < lst.size(); i++) {
            rk[lst.get(i).id] = i + 1;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            int id = fs.nextInt();
            sb.append(rk[id]).append('\n');
        }
        System.out.print(sb);
    }
}

2. 小基 的续航补给

问题描述

小基 要驾驶一辆电动车，从起点 出发，前往距离起点 公里的目的地。

这辆车满电时最多行驶 公里。出发时电量已经是满的，且这部分电量不需要额外付费。

路上共有 个充电站，第 个充电站位于距离起点 公里的位置，在该站每补充 公里的续航需要花费 。

到达某个充电站后，可以选择充入任意数量的电，但电池中的总续航不能超过 公里。

请计算，最少需要额外支付多少充电费用才能到达终点。如果无论怎样规划都到不了终点，输出 。

输入格式

第一行包含三个整数 ，分别表示终点距离、满电续航以及充电站数量。

接下来 行，每行包含两个整数 ，表示第 个充电站的位置和每公里续航的充电单价。

输出格式

输出一个整数，表示到达终点所需的最少额外充电费用。如果无法到达，输出 。

样例输入

20 10 3
4 5
9 2
15 6

20 5 1
10 5

样例输出

24

-1

数据范围

• 
• 
• 
• 
• 
• 

样例	解释说明
样例1	出发时已经自带 公里续航，先开到位置 还剩 。因为位置 的价格更便宜，所以在位置 不用充电。到位置 后，后面 公里内没有更便宜的站点，只能尽量多买，于是在位置 补满到 公里，花费 。到位置 后还差 公里到终点，此时再补 公里，花费 。总费用为 。
样例2	起点到唯一充电站的距离是 ，但满电最多只能行驶 公里，连第一个充电站都到不了，所以无解。

题解

这题和经典加油站问题是同一个模型，只是“油量”换成了“还能跑多少公里的电量”。

真正需要决定的是：每到一个充电站，应该补多少电。

先判断有没有解

如果下面任意一段距离超过了 ，那就说明满电也过不去，答案直接是 ：

• 起点到第一个充电站。
• 相邻两个充电站之间。
• 最后一个充电站到终点。

这个判断是必须先做的，因为一旦中间存在这样的断档，再便宜的充电策略也没有意义。

贪心核心

设当前在第 个充电站，当前位置是 ，当前剩余电量可以支撑 rem 公里。

接下来只需要看一件事：

• 在当前站点满电可达的范围内，是否存在第一个价格比当前站更便宜的站点。

分两种情况讨论。

情况一：能找到更便宜的站点

假设第一个更便宜的站点是 。

此时只需要保证电量刚好够开到 。

原因很直接：如果在当前更贵的站点多买了电，那么这部分电本来可以留到更便宜的站点 再买，显然不会更优。

所以这种情况下：

• 如果当前剩余电量已经够到 ，就一分都不充。
• 否则只补到“恰好能到 ”。

情况二：找不到更便宜的站点

说明从当前站点出发，在满电可达的范围内，所有后继站点都不比它便宜。

那就意味着：未来这段路上迟早要花的钱，放在当前站点买只会更划算，至少不会更亏。

因此这时的最优策略就是：

• 如果终点已经在满电可达范围内，只补到够到终点。
• 否则直接把电量补满。

这正是题目里最关键的贪心结论：

• 找到下一个更便宜站点，就只买到能到它。
• 如果找不到，就尽量补满。

为什么这样贪心一定对

可以把终点看成一个“价格比所有充电站都低的虚拟站点”。

于是每次在当前站点的决策，本质上只有两种：

1. 把购买行为推迟到更便宜的地方。
2. 如果推迟不了，就在当前把未来必须用掉的电先买好。

这个决策不会影响更远处的最优性，因为电量只会沿着路线单向消耗，不存在“绕路回来重新买”的机会。
所以每一站都按照上面的规则做局部最优，最终就会得到全局最优。

实现方法

因为 ，直接对每个站点向后扫描，寻找下一个更便宜的站点即可。

具体流程如下：

1. 读入所有充电站。
2. 检查是否存在长度超过 的断档，若有则输出 。
3. 初始剩余电量为 ，因为出发时已经满电。
4. 依次到达每个充电站，扣掉从上一个位置开过来消耗的电量。
5. 向后寻找满电可达范围内第一个更便宜的站点：
   • 找到：只补到刚好能开到它。
   • 找不到：补到终点可达所需，或者直接补满。
6. 累加费用。

复杂度分析

向后找更便宜站点的过程最坏会扫描所有后继站点，因此时间复杂度是 。

额外只使用了若干变量和数组，空间复杂度是 。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()


def solve():
    line = input()
    if not line:
        return

    l, c, n = map(int, line.split())
    d = [0] * n
    p = [0] * n
    for i in range(n):
        d[i], p[i] = map(int, input().split())

    # 出发时已经满电，若终点本来就在续航内，则不需要任何费用。
    if l <= c:
        print(0)
        return

    # 先判断是否存在无法跨越的空档。
    pre = 0
    for x in d:
        if x - pre > c:
            print(-1)
            return
        pre = x
    if l - pre > c:
        print(-1)
        return

    ans = 0
    rem = c
    pre = 0

    for i in range(n):
        # 先扣掉从上一个位置开到当前站点消耗的电量。
        rem -= d[i] - pre
        pre = d[i]

        # need 表示离开当前站点时，电量至少要达到多少。
        if l - d[i] <= c:
            # 终点已经能直接到达，补到刚好够到终点即可。
            need = l - d[i]
        else:
            j = i + 1
            # 找满电可达范围内第一个更便宜的站点。
            while j < n and d[j] - d[i] <= c:
                if p[j] < p[i]:
                    break
                j += 1

            if j < n and d[j] - d[i] <= c and p[j] < p[i]:
                # 有更便宜站点时，只买到能到它。
                need = d[j] - d[i]
            else:
                # 否则当前站点最划算，直接尽量补满。
                need = c

        if rem < need:
            ans += (need - rem) * p[i]
            rem = need

    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long l, c;
    int n;
    if (!(cin >> l >> c >> n)) {
        return 0;
    }

    vector<long long> d(n), p(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i] >> p[i];
    }

    // 出发自带满电，若终点就在续航范围内，则费用为 0。
    if (l <= c) {
        cout << 0 << '\n';
        return 0;
    }

    // 先检查是否存在任何一段距离超过满电续航。
    long long pre = 0;
    for (int i = 0; i < n; ++i) {
        if (d[i] - pre > c) {
            cout << -1 << '\n';
            return 0;
        }
        pre = d[i];
    }
    if (l - pre > c) {
        cout << -1 << '\n';
        return 0;
    }

    long long ans = 0;
    long long rem = c;
    pre = 0;

    for (int i = 0; i < n; ++i) {
        // 扣掉开到当前站点消耗的电量。
        rem -= d[i] - pre;
        pre = d[i];

        long long need;
        if (l - d[i] <= c) {
            // 已经可以直达终点，只保留刚好够用的电量即可。
            need = l - d[i];
        } else {
            int j = i + 1;
            // 找满电可达范围内第一个更便宜的站点。
            while (j < n && d[j] - d[i] <= c) {
                if (p[j] < p[i]) {
                    break;
                }
                ++j;
            }

            if (j < n && d[j] - d[i] <= c && p[j] < p[i]) {
                // 只买到能到更便宜站点。
                need = d[j] - d[i];
            } else {
                // 后面没有更便宜的，当前站点应尽量多买。
                need = c;
            }
        }

        if (rem < need) {
            ans += (need - rem) * p[i];
            rem = need;
        }
    }

    cout << ans << '\n';
    return 0;
}

• Java

import java.io.IOException;
import java.io.InputStream;

public class Main {
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <=