P1068 [NOIP 2009 普及组] 分数线划定

难度： 普及−
标签： 排序、结构体、模拟、NOIP
来源： 洛谷 P1068

题目背景

本题围绕“[NOIP 2009 普及组] 分数线划定”所描述的场景展开。A 市正在选拔世博会志愿者。

下面的题面采用非逐字重述方式整理，但保留原题中的全部判定条件、边界含义、输入输出要求与特殊约定。

题目描述

A 市正在选拔世博会志愿者。所有报名者先参加笔试，成绩达到面试分数线的人才能进入面试。

若计划录取 $m$ 人，则用于划定分数线的名次为 $m\times150\%$ 向下取整，即

$$k=\left\lfloor 1.5m\right\rfloor=\left\lfloor\frac{3m}{2}\right\rfloor.$$

把所有考生按以下规则排序：

1. 笔试成绩从高到低；
2. 成绩相同时，报名号从小到大。

排名第 $k$ 的考生分数就是面试分数线。所有成绩不低于该分数线的考生都能进入面试，因此遇到与分数线同分的考生时，实际进入面试的人数可能超过 $k$。

请输出分数线、实际进入面试的人数，以及所有进入面试考生的报名号和成绩。

完整规则与任务要求

处理本题时，必须同时满足下列全部要求，不能只实现其中一部分：

• A 市正在选拔世博会志愿者。
• 所有报名者先参加笔试，成绩达到面试分数线的人才能进入面试。
• 若计划录取 $m$ 人，则用于划定分数线的名次为 $m\times150\%$ 向下取整，即 把所有考生按以下规则排序：。
• 1. 笔试成绩从高到低；。
• 2. 成绩相同时，报名号从小到大。
• 排名第 $k$ 的考生分数就是面试分数线。
• 所有成绩不低于该分数线的考生都能进入面试，因此遇到与分数线同分的考生时，实际进入面试的人数可能超过 $k$。
• 请输出分数线、实际进入面试的人数，以及所有进入面试考生的报名号和成绩。
• 分数线名次为 $\left\lfloor1.5m\right\rfloor$。
• 与分数线同分的全部考生都进入面试，因此实际人数可能超过该名次。
• 排序先按成绩降序，再按报名号升序。

程序应完整读取“输入格式”中规定的所有数据，并严格按照“输出格式”给出结果。题目中的区间端点、编号起点、排序优先级、同分处理、空结构处理、取模方式和特殊字符串，均以本题面明确写出的规则为准。

所有算法还必须覆盖“数据范围”中的最小规模、最大规模及边界情况，不能只针对样例或小数据。

输入格式

第一行输入两个整数 $n,m$：

• $n$ 表示参加笔试的考生总数；
• $m$ 表示计划录取人数。

接下来 $n$ 行，每行输入两个整数 $k,s$，分别表示一名考生的报名号和笔试成绩。所有报名号互不相同。

输出格式

第一行输出两个整数：面试分数线和实际进入面试的人数。

接下来按“成绩从高到低、同分报名号从小到大”的顺序，每行输出一名进入面试考生的报名号和成绩。

输入输出样例

6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88

88 5
1005 95
2390 95
1000 90
1001 88
3239 88

样例说明

计划录取 $3$ 人，$\lfloor3\times1.5\rfloor=4$，第 $4$ 名成绩是 $88$，因此分数线为 $88$。共有 $5$ 人成绩不低于 $88$，所以这 $5$ 人全部进入面试。

数据范围

• $5\le n\le 5000$；
• $3\le m\le n$；
• 保证 $\lfloor1.5m\rfloor\le n$；
• 报名号满足 $1000\le k\le 9999$；
• 成绩满足 $1\le s\le 100$；
• 所有报名号互不相同。

本题来源于 NOIP 2009 普及组第二题。

边界与子任务说明

• 测试数据可能覆盖题面允许的最小值、最大值、重复值、空结果、无解或极端结构等边界情形。
• 若原题未额外列出分档子任务，则所有测试点统一遵守上述完整数据范围；若题面已经列出比例或分档条件，则这些条件均应视为题面的一部分。
• 不能根据公开样例推断未写出的额外限制。

本题面依据洛谷 P1068 的公开题目信息重新整理，为内容完整的非逐字重述版。