DNA Sorting
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 83069 |
|
Accepted: 33428 |
Description
One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).
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
The 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
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
Source
East Central North America 1998
一道简单的排序题，题目意思就是求逆序数，先求出每一段DNA序列的逆序数，然后对逆序数进行排序，然后就输出排好序之后的NDA序列；
这里进行求逆序数的有一种方法很巧妙，因为题目中只有4个字母，所以就用到了这种特殊性，我们可以得到O(n)求逆序数的方法，这就需要我们平时的多积累，和我们平时用归并排序或者用树状数组都要方便，对实际问题要进行具体分析；
下面是O(n)的求逆序数的代码；
#include
#include
#include
using namespace std; struct node { char s[100];//储存DNA序列 int sum;//储存每个DNA序列的逆序数 }a[100]; bool cmp(node x,node y)//比较函数 { return x.sum
= 0; i--) { switch (str[i]) { case 'A': a[1]++; a[2]++; a[3]++; break; case 'C': a[2]++; a[3]++; cnt += a[1]; break; case 'G': a[3]++; cnt += a[2]; break; case 'T': cnt += a[3]; } } return cnt; } int main() { int m,n,i,j; scanf("%d%d",&n,&m); for(i=0;i
由于这道题目的数据量不算太大，直接用朴素的求逆序数也能过；
逆序数就是看这个数前面有多少个数比当前的数大，这里直接用了一个二重循环；
#include
#include
using namespace std; struct f{ int num; char w[50]; }s[101]; bool cmp(struct f a, struct f b){ return a.num < b.num; } int main(){ int i, len, n, j, k; cin>>len>>n; for(i = 0; i < n; i++){ s[i].num = 0; cin>>s[i].w; for(j = 1; j < len; j++) for(k = 0; k < j; k++) if(s[i].w[j] < s[i].w[k])//求逆序数 s[i].num++; } sort(s, s+n, cmp); for(i = 0; i < n; i++) cout<