DNA排序

总时间限制: 

1000ms

内存限制: 

65536kB

描述

现在有一些长度相等的DNA串（只由ACGT四个字母组成），请将它们按照逆序对的数量多少排序。

逆序对指的是字符串A中的两个字符A[i]、A[j]，具有i < j 且 A[i] > A[j] 的性质。如字符串”ATCG“中，T和C是一个逆序对，T和G是另一个逆序对，这个字符串的逆序对数为2。

输入

第1行：两个整数n和m，n(0<n<=50)表示字符串长度，m(0<m<=100)表示字符串数量

第2至m+1行：每行是一个长度为n的字符串

输出

按逆序对数从少到多输出字符串，逆序对数一样多的字符串按照输入的顺序输出。

样例输入

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

样例输出

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

思路：

  这道题和我讲的上一道题一样“求逆序对数”，这道题也是求逆序对数，所以也要用上一道题的归并排序函数（用来求逆序对数量）

int merge(int a[],int s,int m,int e) {
    vector<int> a1;
    int m1=s,m2=m+1,c=0;
    while(m1<=m&&m2<=e){
        if(a[m1]>a[m2]){
            c+=m-m1+1;
            a1.push_back(a[m2]);
            m2++;
        }
        else{
            a1.push_back(a[m1]);
            m1++;
        }
    }
    while(m1<=m){
        a1.push_back(a[m1]);
        m1++;
    }
    while(m2<=e){
        a1.push_back(a[m2]);
        m2++;
    }
    int k=0;
    for(int i=s;i<=e;i++) a[i]=a1[k++];
    return c;
}
int solve(int a[],int s,int e) {
    if(s>=e) return 0;
    int m=(s+e)/2;
    int l=solve(a,s,m);
    int r=solve(a,m+1,e);
    int l_r=merge(a,s,m,e);
    return l+r+l_r;
}

  我们上一道题编是的数字，这道题是字符串，我们就要把函数改了吗？

  其实并不需要，因为我们可以新建立一个int数组，存的是输入字符串的int强制转换过的数字（也就是ASCII码），然后放入这个函数中来求逆序对数就行了， 然后用一个变量存下来。

  因为存字符串的int强制转换的ASCII码用一次就行了，所以不需要一直存下来，就可以写一个局部变量！

	for(int x=0;x<m;x++){
		cin>>sum[x].a;
		int b[n];
		for(int i=0;i<n;i++)
		  b[i]=(const int)sum[x].a[i];
		sum[x].i=solve(b,0,n-1);
	}

  现在又要进行排序了，不对，普通的sort好像又解决不了，只能用结构排序来保证不乱，所以我们要写一个结构DNA，里面存什么呢？

  首先是一个i，代表着这个字符串的逆序对个数，第二个就是一个char的数组，我们输入就输入这个数组，我们就需要建立一个结构变量数组，DNA sum[M](m的最大值就是M)。

struct DNA{
	int i;
	char a[M];
};

   接着，我们该写结构排序的声明函数了，因为这道题是以当前字符串的逆序对数来排序的，并且是从小到大，所以我们这个函数应该返回的是参数1.i<参数2.i。

int cmp(DNA a,DNA b){
	return a.i<b.i;
}

  然后，在sort函数中引用以上的函数，执行完过后，这个结构数组就按照逆序对数量的大小进行排序了，只需要循环输出a数组就行了。

DNA排序代码：

#include<bits/stdc++.h>
using namespace std;
const int M=105;
int merge(int a[],int s,int m,int e) {
    vector<int> a1;
    int m1=s,m2=m+1,c=0;
    while(m1<=m&&m2<=e){
        if(a[m1]>a[m2]){
            c+=m-m1+1;
            a1.push_back(a[m2]);
            m2++;
        }
        else{
            a1.push_back(a[m1]);
            m1++;
        }
    }
    while(m1<=m){
        a1.push_back(a[m1]);
        m1++;
    }
    while(m2<=e){
        a1.push_back(a[m2]);
        m2++;
    }
    int k=0;
    for(int i=s;i<=e;i++) a[i]=a1[k++];
    return c;
}
int solve(int a[],int s,int e) {
    if(s>=e) return 0;
    int m=(s+e)/2;
    int l=solve(a,s,m);
    int r=solve(a,m+1,e);
    int l_r=merge(a,s,m,e);
    return l+r+l_r;
}
struct DNA{
	int i;
	char a[M];
};
int cmp(DNA a,DNA b){
	return a.i<b.i;
}
int main(){
	DNA sum[M];
	int n,m;
	cin>>n>>m;
	for(int x=0;x<m;x++){
		cin>>sum[x].a;
		int b[n];
		for(int i=0;i<n;i++)
		  b[i]=(const int)sum[x].a[i];
		sum[x].i=solve(b,0,n-1);
	}
	sort(sum,sum+m,cmp);
	for(int x=0;x<m;x++) cout<<sum[x].a<<endl;
	return 0;
}

  之后，我还会讲解3~4题的排序题目！

该题链接：

OpenJudge - 5:DNA排序http://dsalgo.openjudge.cn/sort/5/