Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 77786 | Accepted: 31201 |
Description
You are responsible for cataloguing a sequence of DNA strings
(sequences containing only the four letters A, C, G, and T). However,
you want to catalog them, not in alphabetical order, but rather in order
of ``sortedness'', from ``most sorted'' to ``least sorted''. All the
strings are of the same length.
Input
first line contains two integers: a positive integer n (0 < n <=
50) giving the length of the strings; and a positive integer m (0 < m
<= 100) giving the number of strings. These are followed by m lines,
each containing a string of length n.
Output
the list of input strings, arranged from ``most sorted'' to ``least
sorted''. Since two strings can be equally sorted, then output them
according to the orginal order.
Sample Input
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
Sample Output
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
中文翻译:
1007 DNA 排序
题目大意:
序列“未排序程度”的一个计算方式是元素乱序的元素对个数。例如:在单词序列“DAABEC'”中,因为D大于右边四个单词,E大于C,所以计算结果为5。这种计算方法称为序列的逆序数。序列“AACEDGG”逆序数为1(E与D)——近似排序,而序列``ZWQM'' 逆序数为6(它是已排序序列的反序)。
你的任务是分类DNA字符串(只有ACGT四个字符)。但是你分类它们的方法不是字典序,而是逆序数,排序程度从好到差。所有字符串长度相同。
输入:
第一行包含两个数:一个正整数n(0<n<=50)表示字符串长度,一个正整数m(0<m<=100)表示字符串个数。接下来m行,每行一个长度为n的字符串。
输出:
输出输入字符串列表,按排序程度从好到差。如果逆序数相同,就原来顺序输出。
样例输入:
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
样例输出:
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
解决思路
这是一道比较简单的排序题,我用的是选择排序。
源码
/*
poj 1000
version:1.0
author:Knight
Email:S.Knight.Work@gmail.com
*/ #include<cstdio> using namespace std; struct _stru_DNA { char String[]; int Measure; }; _stru_DNA DNA[]; int n,m; //计算第Index条DNA的Measure void CountMeasure(int Index); //DNA排序 void SortDNA(); int main(void) { int i; scanf("%d%d", &n, &m); for (i=; i<m; i++) { scanf("%s", DNA[i].String); CountMeasure(i); //printf("%d\n", DNA[i].Measure); } SortDNA(); for (i=; i<m; i++) { printf("%s\n", DNA[i].String); //printf("%d\n", DNA[i].Measure); } return ; } //计算第Index条DNA的Measure void CountMeasure(int Index) { int i,j; int Measure = ; for (i=; i<n-; i++) { if ('A' == DNA[Index].String[i]) { continue; } for (j=i+; j<n; j++) { if (DNA[Index].String[i] > DNA[Index].String[j]) { Measure++; } } } DNA[Index].Measure = Measure; } //DNA排序 void SortDNA() { int i,j; int MinIndex; _stru_DNA Tmp; for (i=; i<m-; i++) { MinIndex = i; for (j=i+; j<m; j++) { if (DNA[j].Measure < DNA[MinIndex].Measure) { MinIndex = j; } } Tmp = DNA[i]; DNA[i] = DNA[MinIndex]; DNA[MinIndex] = Tmp; } }