【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e544
【解題想法】
- 函式 calUnsortedness( )：依題意計算每個字串的”unsortedness”。
- 輸出時，如果多個字串的反轉數(unsortedness)相同，以輸入順序排序。因此必須紀錄每個字串的順序排序(id)。
#include <iostream>
#include <algorithm>
using namespace std;
struct Data{
string s;
int id, unsortedness;
};
int calUnsortedness(string s){
int ret = 0;
for (int i = 0; i < s.size(); i++){
int cnt = 0;
for (int j = i+1; j < s.size(); j++){
if (s[j] < s[i]) cnt++;
}
ret += cnt;
}
return ret;
}
bool cmp(Data a, Data b){
if (a.unsortedness != b.unsortedness) return a.unsortedness < b.unsortedness;
else return a.id < b.id;
}
int main() {
int T, n, m;
cin >> T;
while (T--){
cin >> n >> m;
Data data[m];
for (int i = 0; i < m; i++){
cin >> data[i].s;
data[i].id = i;
data[i].unsortedness = calUnsortedness(data[i].s);
}
sort(data, data+m, cmp);
for (auto i: data){
cout << i.s << "\n";
}
}
return 0;
}