题目描述

在计算机中，磁盘的容量常用的单位有 M (MB)，G (GB)，T (TB)，它们之间的换算关系如下：

• 1T = 1024G
• 1G = 1024M

现给定 n 块磁盘的容量，每块容量可能由多个单位组成，单位可以是 M、G 或 T。要求按照从小到大的顺序对磁盘容量进行稳定排序。

解题思路

1. 单位转换：为了能进行排序，我们需要将不同单位的容量统一成同一种单位（例如，统一转换为 M）。这样，可以通过直接比较数字大小来进行排序。

2. 解析字符串：每个磁盘的容量是由一个或多个单位组成的字符串，比如 3M12G9M 表示 3M + 12G + 9M。需要对字符串进行解析并计算总的容量。

3. 字符串处理：为了处理多个单位的情况，可以通过正则表达式或逐个字符扫描的方式提取数值和单位。

复杂度分析

• 时间复杂度：calc 函数需要对每个磁盘字符串进行一次解析，时间复杂度为 O(L)，其中 L 是每个磁盘容量字符串的长度。排序使用的是 O(n log n) 的时间复杂度，其中 n 是磁盘的数量。因此，总时间复杂度是 O(n * L + n log n)。

• 空间复杂度：主要空间消耗来自存储输入的磁盘字符串和排序过程中的临时存储，空间复杂度为 O(n)，其中 n 是磁盘数量。

代码实现

C++

#include <bits/stdc++.h>
using namespace std;

// 计算给定字符串的总容量，返回单位为M的数值
long long calc(string &s) {
    long long ans = 0;
    long long num = 0;

    for (const auto &c: s) {
        if (isdigit(c)) {
            num *= 10; 
            num += c - '0';  // 读取数字
        } else {
            switch (c) {
                case 'M': ans += num; break;  // 处理M单位
                case 'G': ans += num * 1024; break;  // 处理G单位
                case 'T': ans += num * 1024 * 1024; break;  // 处理T单位
            }
            num = 0;  // 重置num为0，准备下一个数字
        }
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    
    vector<string> disks(n);
    for (int i = 0; i < n; i++) {
        cin >> disks[i];  // 输入每块磁盘的容量字符串
    }

    // 稳定排序，根据磁盘容量的大小进行排序
    sort(disks.begin(), disks.end(), [](string a, string b) {
        return calc(a) < calc(b);
    });

    // 输出排序后的结果
    for (const auto &disk: disks) {
        cout << disk << endl;
    }

    return 0;
}

Python

import re

# 计算给定字符串的总容量，返回单位为M的数值
def calc(s):
    total = 0
    pattern = re.compile(r'(\d+)([MGT])')  # 匹配数字后跟单位M、G、T

    for match in pattern.findall(s):
        num = int(match[0])
        unit = match[1]
        if unit == 'M':
            total += num
        elif unit == 'G':
            total += num * 1024
        elif unit == 'T':
            total += num * 1024 * 1024
    
    return total

# 主函数
def main():
    n = int(input())  # 输入磁盘数量
    disks = [input().strip() for _ in range(n)]  # 输入每个磁盘的容量字符串

    # 稳定排序，根据磁盘容量大小排序
    disks.sort(key=lambda x: calc(x))

    # 输出排序后的磁盘容量
    for disk in disks:
        print(disk)

if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.util.regex.*;

public class Main {
    // 计算给定字符串的总容量，返回单位为M的数值
    public static long calc(String s) {
        long total = 0;
        Pattern p = Pattern.compile("(\\d+)([MGT])");
        Matcher m = p.matcher(s);

        while (m.find()) {
            int num = Integer.parseInt(m.group(1));
            char unit = m.group(2).charAt(0);
            if (unit == 'M') {
                total += num;
            } else if (unit == 'G') {
                total += num * 1024;
            } else if (unit == 'T') {
                total += num * 1024 * 1024;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 输入磁盘数量
        scanner.nextLine();  // 读取换行符

        List<String> disks = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            disks.add(scanner.nextLine().trim());  // 输入磁盘容量字符串
        }

        // 稳定排序，根据磁盘容量的大小排序
        disks.sort((a, b) -> Long.compare(calc(a), calc(b)));

        // 输出排序后的磁盘容量
        for (String disk : disks) {
            System.out.println(disk);
        }
    }
}

题目描述

磁盘的容量单位常用的有 $M$，$G$，$T$ 这三个等级，

它们之间的换算关系为 $1T = 1024G$ ， $1G = 1024M$ ，

现在给定 $n$ 块磁盘的容量，请对它们按从小到大的顺序进行稳定排序，

例如给定 $5$ 块盘的容量，$1T$，$20M$，$3G$，$10G6T$，$3M12G9M$

排序后的结果为 $20M$，$3G$，$3M12G9M$，$1T$，$10G6T$ 。

注意单位可以重复出现，上述 $3M12G9M$ 表示的容量即为 $3M+12G+9M$ ，和 $12M12G$ 相等。

输入描述

输入第一行包含一个整数 $n$($2 <= n <= 100$)，表示磁盘的个数，

接下的 $n$ 行，每行一个字符串(长度大于 $2$ ，小于 $30$ )，

表示磁盘的容量，由一个或多个格式为 $mv$ 的子串组成，

其中 $m$ 表示容量大小， $v$ 表示容量单位，例如 $20M$，$1T$，$30G$，$10G6T$，$3M12G9M$ 。

磁盘容量 $m$ 的范围为 $1$ 到 $1024$ 的正整数，

容量单位 $v$ 的范围只包含题目中提到的 $M$，$G$，$T$ 三种，换算关系如题目描述。

输出描述

输出 $n$ 行，表示 $n$ 块磁盘容量排序后的结果。

样例1

输入

3
1G
2G
1024M

输出

1G
1024M
2G

说明

$1G$ 和 $1024M$ 容量相等，稳定排序要求保留它们原来的相对位置，故 $1G$ 在 $1024M$ 之前。

样例2

输入

3
2G4M
3M2G
1T

输出

3M2G
2G4M
1T

说明

$1T$ 的容量大于 $2G4M$ ，$2G4M$ 的容量大于 $3M2G$ 。