DNA Sorting

coding>C++
1.8k 词

题目描述

One measure of “unsortedness” in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC’’, this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG’’ has only one inversion (E and D)—it is nearly sorted—while the sequence ``ZWQM’’ has 6 inversions (it is as unsorted as can be—exactly the reverse of sorted).
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness’’, from ``most sorted’’ to ``least sorted’’. All the strings are of the same length.

输入

The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

输出

Output the list of input strings, arranged from ``most sorted’’ to ``least sorted’’. Since two strings can be equally sorted, then output them according to the orginal order.

样例输入

1
2
3
4
5
6
7
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

样例输出

1
2
3
4
5
6
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <set>
using namespace std;
int nixushu(const string &s) {//逆序数
    int t = 0;
    for (int i = 0; i < s.size() - 1; i++)
        for (int j = i + 1; s[j]; j++)
            if (s[i] > s[j]) t++;
    return t;
}

typedef struct stu {
    string DNA;
    bool operator<(const stu &i) const{
        return nixushu(DNA)< nixushu(i.DNA);
    }
} stu;

int main() {
    int n, m;
    cin >> n >> m;
    multiset<stu>ms;
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        ms.insert(stu{s});
    }
    for(auto &i:ms)
        cout<<i.DNA<<endl;
}