首页 > 代码库 > openJudge
openJudge
1007:DNA排序
描述
现在有一些长度相等的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 6AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT
样例输出
CCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAA
解：
#include <iostream>#include <algorithm>using namespace std;typedef struct{ string dna; int count;}DNA;DNA dna[101];int cmp(const void *a,const void *b){ DNA *aa = (DNA *)a; DNA *bb = (DNA *)b; return aa->count-bb->count;}int main(){ int n,m; char c; cin>>n>>m; for(int i = 0; i < m; i++) { cin>>dna[i].dna; dna[i].count = 0; for(int j = 0; j < n; j++) for(int k = j+1; k < n; k++) { if(dna[i].dna[j]>dna[i].dna[k]) dna[i].count++; } } qsort(dna,m,sizeof(dna[0]),cmp); for(int i = 0; i < m; i++) cout<<dna[i].dna<<endl; return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。