牛半仙的妹子串

题目描述

牛半仙有 $n$ 个妹子，每个妹子有一个名字（只含小写字母、长度不超过 50）和一个评分。他要回答 $m$ 个询问 $(x, k)$ ：名字以字母 $x$ 结尾的妹子中评分第 $k$ 大的妹子的名字，评分相同时先读入的算评分更大；这样的妹子不足 $k$ 个时输出 Orz YYR tql。输入第一行 $n, m$ ，接下来 $n$ 行每行一个名字和评分，接下来 $m$ 行每行一个字母 $x$ 和正整数 $k$ 。 $n, m \leqslant 10^5$ ， $k \leqslant n$ 。

样例：输入 5 2 / aaa 1 / aa 2 / a 3 / ab 3 / bb 4 / b 2 / a 4，输出 ab / Orz YYR tql。

思路

名字结尾字母只有 26 种，读入时按结尾字母分 26 个桶，每个桶内按「评分降序、同分先读入在前」排好序，排序后桶内第 $k$ 个元素就是该字母下第 $k$ 大的名字。询问时桶内不足 $k$ 个就输出 Orz YYR tql，否则按下标直接取名字，单次询问 $O(1)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 17:40
# update_at: 2026-10-04 09:12

import sys
from collections import defaultdict

ORZ = b"Orz YYR tql"  # 该结尾字母下凑不够第 k 名时的回答


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())  # token 流：名字与数字都按 next() 顺序消费
    n, m = int(next(data)), int(next(data))

    # 按名字结尾字母分桶：排序键 (-评分, 读入序号)，评分大在前、同分先读入在前
    buckets: dict[str, list[tuple[int, int, bytes]]] = defaultdict(list)
    for i in range(2, 2 + 2 * n, 2):
        name = next(data)
        buckets[name[-1:]].append((-int(next(data)), i, name))
    for ranked in buckets.values():
        ranked.sort()

    out: list[bytes] = []
    for j in range(2 * n, 2 * n + 2 * m, 2):
        ranked = buckets.get(next(data))  # 询问的结尾字母
        k = int(next(data))
        out.append(ranked[k - 1][2] if ranked is not None and len(ranked) >= k else ORZ)

    sys.stdout.buffer.write(b"\n".join(out) + b"\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 21:38
 * update_at: 2026-10-04 21:38
 */
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

struct Girl {
    ll score;   // 评分
    ll id;      // 读入编号，从 1 开始
    string name;
};

vector<Girl> bucket[26]; // bucket[c] 存放名字以字符 'a' + c 结尾的妹子
ll cnt[26];             // cnt[c] = bucket[c] 中的元素个数

// 排序比较：评分大的在前，评分相同时先读入（编号小）的在前
bool cmp_girl(const Girl &a, const Girl &b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;
}

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

    ll n, m;
    cin >> n >> m;

    // 读入时按名字的最后一个字母分桶，顺便记下读入编号
    for (ll i = 1; i <= n; i++) {
        string name;
        ll score;
        cin >> name >> score;
        int c = name[name.size() - 1] - 'a';
        Girl g;
        g.score = score;
        g.id = i;
        g.name = name;
        bucket[c].push_back(g);
        cnt[c]++;
    }

    // 每个桶内部排好序，桶内下标 k - 1 就是该字母下第 k 大的名字
    for (int c = 0; c < 26; c++) {
        sort(bucket[c].begin(), bucket[c].end(), cmp_girl);
    }

    for (ll q = 1; q <= m; q++) {
        char x;
        ll k;
        cin >> x >> k;
        int c = x - 'a';
        if (k > cnt[c]) {
            cout << "Orz YYR tql" << endl;
        } else {
            cout << bucket[c][k - 1].name << endl;
        }
    }

    return 0;
}

目录

题目描述

思路

参考代码