题目描述

一个序列中的“未排序”的度量是相对于彼此顺序不一致的条目对的数量，例如，在字母序列“DAABEC”中该度量为5，因为D大于其右边的4个字母，E大于其右边的1个字母。该度量称为该序列的逆序数。序列“AACEDGG”只有一个逆序对(E和D)，它几乎被排好序了，而序列“ZWQM”有6个逆序对，它是未排序的，恰好是反序。
需要对若干个DNA序列（仅包含4个字母A、C、G和T的字符串）分类，注意是分类而不是按字母顺序排列，是按照“最多排序”到“最小排序”的顺序排列，所有DNA序列的长度都相同。

输入

第一行包括两个整数，n(0<n≤200）表示字符串长度，m(0<m≤200)表示字符串个数，两个数之间个一个空格；后面是m行，每行包括一个长度为n的字符串。

输出

按“最多排序”到“最少排序”的顺序输出所有字符串。若两个字符串的逆序对个数相同，按原始顺序输出它们！

样例输入

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

样例输出

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

思路：本题其实就是求每一个字符串的逆序对数目，然后根据逆序对数目进行排序，所以用归并排序对每一个字符串计算逆序对数目即可

#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 210;
typedef pair<int,int> pii;
string a[N];
pii sort_string[N];//存储不同逆序对和对应的字符串数组下标
int cnt = 0;
void merge(string &k,int l,int r)
{
    if(l >= r) return;
    int mid = l + r>>1;
    merge(k,l,mid),merge(k,mid+1,r);
    int i = l, j = mid+1;
    string temp;
    while(i <= mid && j <= r)
    {
        if(k[i] <= k[j]) temp  += k[i++];
        else{
            cnt += (mid - i + 1);
            temp  += k[j++];
        }
    }
    while(i <= mid) temp += k[i++];
    while(j <= r) temp += k[j++];
    for(i = 0, j = l; j <= r; i++, j++) k[j] = temp[i];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < m; i++)
        cin>>a[i];

    for(int i = 0; i < m; i++)
    {
        cnt = 0;
        string temp = a[i];
        merge(temp,0,n-1);
        sort_string[i].first = cnt;//得到当前序列的逆序对个数
        sort_string[i].second = i;
    }
    sort(sort_string,sort_string + m);
    for(int i = 0; i < m; i++)
    {
        int temp;
        temp = sort_string[i].second;
        cout<<a[temp]<<endl;
    }
    return 0;
}