贝壳找房 · 排序 · 算法编程题
贝壳找房 排序 n ≤ 1e3 时限 2 秒 / 64 MB

题目描述

牛牛参加了这个赛季的牛王挑战赛,这个赛季一共有 n 只队伍参赛,每只队伍都会与其它队伍进行一场三局两胜的较量,赢一大场则大场分数 + 1 ,赢一小场则小场分数 + 1 ,输一小场则小场分数 - 1 ,在所有比赛结束之后,大场得分高的排名靠前,否则小场得分高的排名靠前,特殊的,如果有两支队伍大场、小场得分均相同,那么他们最终排名相同,而在最终排名上出现的次序按照队名字典序顺序。
你为了帮助牛牛预测排名,特意写了一个能够快速排序的算法,牛妹为了测试该算法的正确性,给出了若干组数据。

输入输出

输入描述
本题为多组测试数据,第一行输入一个正整数 T( 1≤ T≤ 1000) ,代表测试数据的组数。
对于每个测试数据,第一行输入一个正整数 n( 1≤ n≤ 1000) ,代表参赛战队数量。
接下去 n 行,每行代表一个战队的赛季对战信息,信息第一行输入一个仅由小写字母组成的字符串 s( 1≤ s≤ 10) ,两个整数 a, b( 0≤ a, b≤ 1000) ,分别代表该战队的队名,大场得分以及小场得分。
输出描述
对于每个测试数据,在一行内按照赛季总排名从前到后的顺序输出 n 支战队的队名。

样例共 1 组

样例 1
输入
1
4
nowcoder 2 4
new 1 2
ss 1 2
now 1 2
输出
nowcoder new now ss

算法解析依据充分

考点:排序

数据规模 n ≤ 1e3 | 限制 2 秒 / 64MB | 标准输入输出

题目画像

  • 数据规模:T ≤ 1e3,n ≤ 1e3
  • 元素值域:a ≤ 1e3,b ≤ 1e3,s ≤ 10(注意整数类型选择,避免溢出)
  • 复杂度门槛:允许 O(n²);若 n ≤ 300,O(n³) 通常也跑得动,需看具体常数。
  • 源站时限:2 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:排序

本题切入点

先按规则统计每队的大场分与小场分,再按「大场分降序、小场分降序、队名字典序升序」多关键字排序。

先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。

思路框架(排序 通法 · 非本题专属)

  1. 排序后很多性质变简单:相邻关系、前缀性质、二分可行。
  2. 若题目禁止使用排序库函数,则手写快排/归并(归并还能顺带求逆序对)。
  3. 排序常与其他范式组合,比如「排序 + 贪心」「排序 + 二分」「排序 + 双指针」。

实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。

复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)

该范式的通法易错点

  • 自定义比较函数不满足严格弱序会导致运行时崩溃。
  • 排序后丢失原始下标,题目需要下标时记得用 pair 一起排。

对照本题

  • 数据规模 n ≤ 1e3,允许 O(n²);若 n ≤ 300,O(n³) 通常也跑得动,需看具体常数。
  • 元素值域最大到 1e3 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入:1 / 4 / nowcoder 2 4 / new 1 2 / ss 1 2 / now 1 2
  • 输出:nowcoder new now ss

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:贝壳找房2023届校招移动端类试卷。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解