P2553. 磁盘容量

解题思路

本题也是属于 lambda 匿名函数 在 sort() 方法中的运用，主要考察基础语法。本题排序有两个依据：

• 磁盘容量大小
• 在原数组中的位置

因此我们需要将所有输入的磁盘容量字符串 s 转换为统一的单位。 注意到最小的单位是 M，故应该将所有输入的磁盘容量转化为以 M 为单位的数值。 该过程可以通过以下的 convert(s) 函数来完成：

另外，由于要求了 稳定排序，在原数组中的索引也应该被记录，故在储存输入时应该同时储存 s 和 i：

在排序过程中，使用 lambda 匿名函数 对排序依据进行指定，先依据 convert(s)，再依据下标 i 进行排序。即：

复杂度分析 设 n 为磁盘数量，L 为单个容量字符串的长度。convert 函数逐字符扫描一个容量字符串：数字字符累积进 num，遇到单位字符就按 M 为 1、G 为 1024、T 为 1024×1024 的倍率把 int(num) 结算进 total 并清空 num，单次调用是 O(L)。Python 版排序时，sort 的 key 函数对每个元素只求值一次，因此 convert 总共只被调用 n 次，换算共花 O(n×L)；之后排序比较的是 (换算数值, 原下标) 元组，单次比较为常数代价，排序本身 O(n log n)。总时间复杂度为 O(n×L + n log n)，瓶颈在逐串换算与排序这两步。需要留意的是 C++ 参考代码把 convert 写在了比较器里，每次比较都要重新换算两个字符串，实际是 O(n log n × L)，数据量大时不如 Python 版「先算好键再排序」的方式高效。空间上，lst 存 n 个（字符串, 下标）对，空间复杂度为 O(n)。