2014-08-22
题目意思：
按照各个字符串的逆序数排序（稳定排序，即若A=B，则AB的顺序还是原来的样子）
思路：
求出每个字符串的逆序数后，排序输出即可
代码：
//Memory Time
// 352K 16MS #include <stdio.h>
#include <stdlib.h> typedef struct Dna{
int num;
char sequence[];
}DNASQ; //计算逆序数
int count(char sq[],int len){
int a,c,g,i;
int count;
a=c=g=;
for(i=len-;i>=;i--){
switch (sq[i]){
case 'A':
{
a++;
break;
}
case 'C':
{
c++;
count+=a;
break;
}
case 'G':
{
g++;
count=count+a+c;
break;
}
case 'T':
{
count=count+a+c+g;
break;
}
default:
break;
}
}
return count;
} int partition(DNASQ sq[],int left,int right){
int i=left;
int j=right;
DNASQ temp=sq[i];
while(i!=j){
while(sq[j].num>=temp.num&&i<j)
j--;
while(sq[i].num<=temp.num&&i<j)
i++;
if(i<j)
{
DNASQ t;
t=sq[i];
sq[i]=sq[j];
sq[j]=t;
}
}
sq[left]=sq[i];
sq[i]=temp;
return i;
}
//快排
void qSort(DNASQ sq[],int left,int right){
int dq=;
if(left<right){
dq=partition(sq,left,right);
qSort(sq,left,dq-);
qSort(sq,dq+,right);
}
} int main(){
DNASQ dnasq[];
int n,m,i;
scanf("%d%d",&n,&m);
for(i=;i<m;i++){
scanf("%s",dnasq[i].sequence);
dnasq[i].num=count(dnasq[i].sequence,n);
}
qSort(dnasq,,m-);
for(i=;i<m;i++){
printf("%s\n",dnasq[i].sequence);
}
return ;
}
PS：这题由于字符串中只含有AGCT四个字母，所以在求逆序数的时候可以直接计数就行了。