首页 > 代码库 > POJ1007
POJ1007
2014-08-22
题目意思：
按照各个字符串的逆序数排序（稳定排序，即若A=B，则AB的顺序还是原来的样子）
思路：
求出每个字符串的逆序数后，排序输出即可
代码：
//Memory Time // 352K 16MS #include <stdio.h>#include <stdlib.h>typedef struct Dna{ int num; char sequence[50];}DNASQ;//计算逆序数int count(char sq[],int len){ int a,c,g,i; int count; a=c=g=0; for(i=len-1;i>=0;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=0; if(left<right){ dq=partition(sq,left,right); qSort(sq,left,dq-1); qSort(sq,dq+1,right); }}int main(){ DNASQ dnasq[100]; int n,m,i; scanf("%d%d",&n,&m); for(i=0;i<m;i++){ scanf("%s",dnasq[i].sequence); dnasq[i].num=count(dnasq[i].sequence,n); } qSort(dnasq,0,m-1); for(i=0;i<m;i++){ printf("%s\n",dnasq[i].sequence); } return 0;}
PS：这题由于字符串中只含有AGCT四个字母，所以在求逆序数的时候可以直接计数就行了。
POJ1007
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。