POJ1007---DNA sorting解法

该题是POJ第1007，大概ratio在38%左右，分析一下我写的代码。

先看看题目

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

先说一下，该题在不少online judgement都有，但是我测试了，在POJ我这个能AC，在ZOJ世死活得到runtime error的，可见POJ可能对很多边界测试比较苛刻的呵呵，大家参考一下代码吧

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<memory.h>

void swap(char **a,char **b);

int
main(){
    
    int length,count,i = 0,j=0,k=0;
    //检测输入条件

    while(1){
        if(scanf("%d %d",&length,&count) == 2 && length>0 && length<=50 && count>0 && count <=100)
            break;
    }
            

    int savecount = count;
    char **str;
    int mask[count];
    char buf[length+1];

    for(i=0;i<count;i++)
        mask[i] = 0;
        
    //分配空间    

    str = (char **)malloc(sizeof(char *)*count);
    for(i=0;i<count;i++)
        str[i] = (char *)malloc(sizeof(char)*length+1);
    

    i = 0;
    /*依靠一个数组存储每个字符串的所谓的可逆序数目*/
    while(count--){
        scanf("%s",buf);
        strncpy(str[i],buf,length+1);
        j = 0,k = 0;
        for(;j<length;j++)
            for(k=j+1;k<length;k++)
                    if(str[i][j] > str[i][k])
                        mask[i]++;
        i++;

    }
    /*这里的思想是，依靠对mask的排序，完成对str的排序
    关键的是mask的值也是需要swap的，不然后来继续进行就会杂乱了*/
    for(i=0;i<savecount;i++)
        for(j=i+1;j<savecount;j++)
            if(mask[i]>mask[j]){
                swap(&str[i],&str[j]);    
                k = mask[i];
                mask[i] = mask[j];
                mask[j] = k;
            }
    //输出            

    for(i=0;i<savecount;i++){
        for(j=0;j<length;j++)
            printf("%c",str[i][j]);
        printf("\n");
    }

    system("pause");
    return 0;
}

void swap(char **a,char **b){
    
    char *temp = *a;
    *a = *b;
    *b = temp;    
}