拼多多笔试题 20260315 第一题

第一题：直播排行榜

题目

多多负责多多直播的首页直播排行榜的巡检工作。今天平台一共收到 n 条候选直播内容，按输入顺序依次编号为 1 到 n。每条直播内容都属于某个主播。为了避免同一主播同时占据多个直播排行榜位置，正式生成榜单前，平台会先做一次主播去重：

• 对于同一个主播，只保留该主播最优的一条直播内容进入候选榜单；
• 同一主播的其他直播内容会在这一步直接被淘汰，不再参与后续排序。

因此，最终直播排行榜中每个主播至多出现一次，榜单条数恰好等于不同主播的个数。

一条直播内容是否更优，按以下顺序比较：

1. 点赞数更多者更优；
2. 如果点赞数相同，则评论数更多者更优；
3. 如果点赞数和评论数都相同，则发布时间更早者更优（t_i 越小表示发布时间越早）；
4. 如果以上三项仍然完全相同，则原始编号更小者更优。

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

现在给出 q 个查询。每次查询一条直播内容的最终结果：

• 如果这条直播条目最终出现在直播排行榜中，输出它的排名；
• 如果它在主播去重阶段已经被淘汰，输出 0。

输入描述

第一行输入两个整数 n, q，分别表示候选直播内容数和查询条数。

接下来 n 行，第 i 行输入四个整数 u_i, a_i, b_i, t_i，表示第 i 条直播内容所属主播编号、点赞数、评论数和发布时间。其中，t_i 越小表示发布时间越早。

接下来 q 行，每行输入一个整数 id，表示询问编号为 id 的直播内容最终排名。

输出描述

输出 q 行，每行一个整数：若对应直播条目最终上榜，输出其排名，排名从 1 开始计数；否则输出 0。

补充说明

• 1 ≤ n, q ≤ 2×10^5
• 1 ≤ u_i ≤ 10^9
• 0 ≤ a_i, b_i, t_i ≤ 10^9
• 1 ≤ id ≤ n

样例输入

复制代码

样例输出

复制代码

样例说明

主播 1 有第 1、3 两条直播条目，其中第 3 条更优；主播 2 有第 2、5 两条直播条目，其中第 5 条更优；主播 3 只有第 4 条直播条目。因此候选榜单只剩第 3、4、5 条直播条目，再按规则排序后顺序为 3 > 5 > 4。

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        HashMap<Integer, Live> map = new HashMap<>(); // key：主播ID，value：该主播最优直播
        Scanner in = new Scanner(System.in);
        PriorityQueue<Live> pq = new PriorityQueue<>((a, b) -> {
            if (a.a != b.a) return b.a - a.a;
            if (a.b != b.b) return b.b - a.b;
            if (a.t != b.t) return a.t - b.t;
            return b.usedId - a.usedId;
        });
        int n = in.nextInt();
        int q = in.nextInt();
        for (int i = 1; i <= n; i++) {
            int id = in.nextInt();
            int a = in.nextInt();
            int b = in.nextInt();
            int t = in.nextInt();
            Live newer = new Live(i, a, b, t);
            if (map.get(id) == null) {
                map.put(id, newer);
            } else {
                Live older = map.get(id);
                if (!compareABigerThanB(older, newer)) {  //新的比旧的好
                    map.put(id, newer);
                }
            }
        }
        map.forEach((a, b) -> {
            pq.add(b);
        });
        int[] ans = new int[n + 1];
        int rank = 1;
        while (!pq.isEmpty()) {
            Live live = pq.poll();
            ans[live.usedId] = rank++;
        }
        for (int i = 0; i < q; i++) {
            int id = in.nextInt();
            System.out.println(ans[id]);
        }
    }

    static boolean compareABigerThanB(Live a, Live b) {
        if (a.a != b.a) return b.a > a.a;
        if (a.b != b.b) return b.b > a.b;
        if (a.t != b.t) return b.t < a.t;
        return false;
    }

    static class Live {
        int usedId, a = -1, b = -1, t = -1;

        Live(int usedId, int a, int b, int t) {
            this.usedId = usedId;
            this.a = a;
            this.b = b;
            this.t = t;
        }
    }


}