M31185: 一道题搞懂内置排序函数

http://cs101.openjudge.cn/practice/31185/

下面是满足题目所有模式与规则的 Python 参考代码。代码使用了 sys.stdin.read 来方便、稳妥地处理各种空白字符与换行。

Python 3 代码

python

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    mode = int(input_data[0])
    rule = int(input_data[1])
    n = int(input_data[2])

    idx = 3

    if mode == 1:
        # 模式 1：整数列表
        arr = [int(input_data[idx + i]) for i in range(n)]
        mx = max(arr)
        mn = min(arr)

        arr.sort(reverse=(rule == 2))

        print(*(arr))
        print(f"{mx} {mn}")

    elif mode == 2:
        # 模式 2：字符串列表
        arr = input_data[idx : idx + n]
        arr.sort(reverse=(rule == 2))

        print(*(arr))

    elif mode == 3:
        # 模式 3：按照二元组两个元素之和排列（稳定排序）
        arr = []
        for _ in range(n):
            a = int(input_data[idx])
            b = int(input_data[idx + 1])
            arr.append((a, b))
            idx += 2

        arr.sort(key=lambda x: x[0] + x[1], reverse=(rule == 2))

        for a, b in arr:
            print(f"{a} {b}")

    elif mode == 4:
        # 模式 4：按照列表中的第二个元素排列（稳定排序）
        arr = []
        for _ in range(n):
            a = int(input_data[idx])
            b = int(input_data[idx + 1])
            c = int(input_data[idx + 2])
            arr.append([a, b, c])
            idx += 3

        arr.sort(key=lambda x: x[1], reverse=(rule == 2))

        for a, b, c in arr:
            print(f"{a} {b} {c}")

    elif mode == 5:
        # 模式 5：保留原来的列表
        arr = [int(input_data[idx + i]) for i in range(n)]

        # 输出原始数据
        print(*(arr))

        # 使用 sorted 生成新列表，不改变原列表
        sorted_arr = sorted(arr, reverse=(rule == 2))
        print(*(sorted_arr))

    elif mode == 6:
        # 模式 6：进行两次稳定排序
        arr = []
        for _ in range(n):
            a = int(input_data[idx])
            b = int(input_data[idx + 1])
            arr.append((a, b))
            idx += 2

        if rule == 1:
            # 第一步：b 降序；第二步：a 升序
            arr.sort(key=lambda x: x[1], reverse=True)
            arr.sort(key=lambda x: x[0], reverse=False)
        else:
            # 第一步：b 升序；第二步：a 降序
            arr.sort(key=lambda x: x[1], reverse=False)
            arr.sort(key=lambda x: x[0], reverse=True)

        for a, b in arr:
            print(f"{a} {b}")


if __name__ == "__main__":
    solve()

知识点解析

稳定排序（Stable Sort）：Python 自带的 Timsort 算法（即 list.sort() 和 sorted()）是稳定排序，当关键字相同时，元素会保留在原序列中的相对顺序。模式 3、4 以及 6 均基于该特性。
key 参数与 lambda 表达式：可以通过 key=lambda x: ... 来指定比较的标准（例如模式 3 中取 x[0] + x[1]，模式 4 中取 x[1]）。
list.sort() 与 sorted()：
- arr.sort() 是就地修改列表，返回值为 None；
- sorted(arr) 会返回一个新的排好序的列表，保持原列表不变（模式 5）。

M31185: 一道题搞懂内置排序函数 ​

M31185: 一道题搞懂内置排序函数