题意：
输入m个长度为n的DNA序列，把他们按照逆序数从小到大稳定排序输出。
PS:“稳定排序”就是当序列中出现A1==A2时，排序前后A1与A2的相对位置不发生改变。
思路：裸归并排序了 不懂得可以参考下 但是他的代码写错了！后来我按照理解自己写了一个，测了一下是对的！
AC代码：
#include<cstdio>#include<cstring>#include<algorithm>#include<string>#include<iostream>using namespace std;const int maxn=100+10;char s1[maxn];struct node{string s;int tot;}num[maxn];int a[105];bool cmp(node x,node y){return x.tot<y.tot;}int b[maxn];int Count;void Merge(int *a, int start, int mid , int end) //归并排序的合并部分{int i = start,j = mid + 1,k = start;while(i <= mid&&j <= end){if(a[i] <= a[j]){b[k++] = a[i++];}else{Count += j – k;b[k++] = a[j++];}}while(i <= mid){b[k++] = a[i++];}while(j <= end){b[k++] = a[j++];}for(int i = start; i <= end; i++){a[i] = b[i];}}void MergeSort(int *a, int start, int end){if(start < end){int mid = (start + end)/2;MergeSort(a,start,mid);MergeSort(a,mid+1,end);Merge(a,start,mid,end);}}int main(){int n,m;scanf("%d %d",&n,&m);for(int i=0;i<m;i++){Count=0;scanf("%s",s1);for(int j=0;j<n;j++){a[j]=s1[j]-'A';}MergeSort(a,0,n-1);num[i].s=s1;num[i].tot=Count;}sort(num,num+m,cmp);for(int i=0;i<m;i++){cout<<num[i].s<<endl;}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
我走得很慢！但我从不后退！
