AlgoMooc
← 返回题库

P2822. 找出作弊的人

中等通过率 36% · 提交 211 · 通过 75
哈希表排序贪心

小慕负责处理公司一次考试的成绩,现在他想初步筛选出可能存在作弊行为的员工。由于员工人数很多,他打算先找出成绩最接近的员工对,再进一步核实。 筛选规则是:找出考试成绩分差最小的员工ID对(p1, p2),并保证p1 < p2。 员工人数取值范围:0 < n < 100000 员工ID为整数,取值范围:0 <= ID <= 100000 考试成绩为整数,取值范围:0 <= score <= 300

提示:带虚线的词点一下有通俗解释。

输入描述

员工的ID及考试分数

输出描述

分差最小的员工ID对(p1,p2)列表,要求p1<p2。每一行代表一个集合,每个集合内的员工ID按顺序排列,多行结果也以员工对中p1值大小升序排列(如果p1相同则p2升序)。

示例

示例 1

输入

5
1 90
2 91
3 95
4 96
5 100

输出

1 2
3 4

说明:输入:第一行为员工个数n,后续的n行第一个数值为员工ID,第二个数值为员工考试分数 输出:员工1和员工2的分差为1,员工3和员工4的分差也为1,因此最终结果为 1 2 3 4

示例 2

输入

5
1 90
2 91
3 92
4 85
5 86

输出

1 2
2 3
4 5

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。