BISHI22　分数线划定¶

简单通过率 44.37%python3样例通过牛客 AC排序

一句话

按成绩降序（同分按报名号升序）排序后，取第 t 名的成绩作分数线。

解题思路¶

这题考什么¶

多关键字排序，外加一个容易读错的定义：分数线是一个分数值，不是一个名次。 t = floor(1.5m) 只用来「定位分数线落在第几名」，真正决定谁进面试的是这个分数值本身，所以凡是成绩不低于它的人都要录取，最终人数一般会多于 t。

Python 里表达「第一关键字降序、第二关键字升序」最省事的办法，是把第一关键字取负后塞进元组：把 (报名号 k, 成绩 s) 存成 (-s, k) 再 sort，元组默认的字典序比较就同时满足了两个方向。这样既不必写比较函数，也避免了「先按报名号排一遍、再按成绩排一遍」这种依赖排序稳定性的绕路写法。自定义排序的更多写法见 12-自定义排序。

数据规模与复杂度¶

n <= 5000，排序 O(n log n) 约 6e4 次比较；读入、筛选、输出都是 O(n)。其他语言时限 2 秒，余量极大。成绩 <= 100、报名号 <= 9999，都是小整数。

坑在哪¶

分数线是「第 t 名的成绩」，不是「前 t 名」。与第 t 名同分的人也要进面试，所以输出人数 cnt >= t；只输出排序后的前 t 个人会漏掉同分者。
t 用 3 * m // 2 而不是 int(1.5 * m)。整除写法不经过浮点，不存在 1.5 * m 落成 x.999... 再被截断的隐患。
约束只保证 m <= n，m 接近 n 时 floor(1.5m) 会超过总人数（n = m = 5 时 t = 7），不用 min(t, n) 夹一下就会下标越界。
排序键必须写成 (-s, k)。若写成 (s, k) 排完再整体反转列表，同分者的报名号顺序也会被一并倒过来，变成从大到小，与题目要求相反。

样例复核¶

n=6, m=3 -> t = floor(4.5) = 4；排序后依次是 (95,1422) (95,8805) (90,9848) (88,4162) (88,6731) (84,7483)，第 4 名成绩 88，故分数线为 88；成绩 >= 88 的共 5 人，输出首行 "88 5" 再跟 5 行名单，与样例一致。

参考实现¶

solutions/BISHI22.py
import sys

# 整块读入再按空白切分：token 依次是 n, m, k1, s1, k2, s2, ...
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
people = []
for i in range(n):
    # 前两个 token 是 n 和 m，所以第 i 个人的两项落在下标 2+2i 与 3+2i
    k = int(data[2 + 2 * i])
    s = int(data[3 + 2 * i])
    people.append((-s, k))          # 成绩取负，让「元组升序」同时表达降序成绩 + 升序报名号
people.sort()                       # 成绩降序、同分报名号升序

t = min(3 * m // 2, n)              # floor(1.5 * m)；m 接近 n 时 t 会超过总人数，需要夹住
line = -people[t - 1][0]            # 排名是 1-based，第 t 名对应下标 t-1；取负还原成真实成绩

out = []
# 分数线定下来之后，只看分数不看名次：>= line 的人全部入选，人数可能超过 t
sel = [(k, -ns) for ns, k in people if -ns >= line]
out.append("%d %d" % (line, len(sel)))
for k, s in sel:
    out.append("%d %d" % (k, s))
sys.stdout.write("\n".join(out) + "\n")

BISHI22 分数线划定¶