题目描述
E卷 100分题型
磁盘的容量单位常用的有 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
输入
32G4M3M2G1T
输出
3M2G2G4M1T
说明
1T的容量大于2G4M，2G4M的容量大于3M2G。
题解
思路：
- 计算每个字符串的值
string -> int方便进行排序是大小比较 - 进行二分排序，书写实现时需要额外注意
排序稳定的要求。(稳定排序的含义：如果数组中两个值相等，排序之后的前后相互关系要和排序前保持一致)
#include<iostream>
#include<vector>
#include<string>
#include <utility>
#include <sstream>
#include<algorithm>
using namespace std;
//将字符串的值转换为Longlong类型
long long calVaue(string s) {long long res = 0;int sum = 0;for (int i = 0; i < s.size(); i++) {if (s[i] >= '0' && s[i] <= '9') {sum = sum * 10 + s[i] - '0';} else {if (s[i] == 'M') {res += sum;} else if (s[i] == 'G'){res += (1024 * sum);} else {res += (1024 * sum * 1024);}sum = 0;}}return res;
}// 快速排序实现
void quickSort(int left, int right, vector<string> & ans) {if (left >= right) {return;}int begin = left;int end = right;string pos = ans[left];while (left < right) {// = 条件视为稳定而特别设置while (left < right && calVaue(pos) <= calVaue(ans[right])) {right--;}if (left < right) {swap(ans[left], ans[right]);left++;}// 不是>=也是为了排序稳定while (left < right && calVaue(pos) > calVaue(ans[left])) {left++;}if (left < right) {swap(ans[left], ans[right]);right--;}}ans[left] = pos;quickSort(begin, left - 1, ans);quickSort(left + 1, end ,ans);
}int main() {int n;cin >> n;vector<string> ans(n);for (int i = 0; i < n; i++) {cin >> ans[i];} quickSort(0, ans.size()-1 ,ans);for (int i = 0; i < n; i++) {cout<<ans[i] <<endl;}return 0;
}
