POJ1007---DNA sorting解法

dengjin

                                                该题是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 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
ATCGATGCATSample Output
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAASource
East Central North America 1998
先说一下，该题在不少online judgement都有，但是我测试了，在POJ我这个能AC，在ZOJ世死活得到runtime error的，可见POJ可能对很多边界测试比较苛刻的呵呵，大家参考一下代码吧
#includestdio.h>
#includestdlib.h>
#includestring.h>
#includememory.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;icount;i++)
        mask = 0;
        
    //分配空间   
    str = (char **)malloc(sizeof(char *)*count);
    for(i=0;icount;i++)
        str = (char *)malloc(sizeof(char)*length+1);
   
    i = 0;
    /*依靠一个数组存储每个字符串的所谓的可逆序数目*/
    while(count--){
        scanf("%s",buf);
        strncpy(str,buf,length+1);
        j = 0,k = 0;
        for(;jlength;j++)
            for(k=j+1;klength;k++)
                    if(str[j] > str[k])
                        mask++;
        i++;
    }
    /*这里的思想是，依靠对mask的排序，完成对str的排序
    关键的是mask的值也是需要swap的，不然后来继续进行就会杂乱了*/
    for(i=0;isavecount;i++)
        for(j=i+1;jsavecount;j++)
            if(mask>mask[j]){
                swap(&str,&str[j]);   
                k = mask;
                mask = mask[j];
                mask[j] = k;
            }
    //输出            
    for(i=0;isavecount;i++){
        for(j=0;jlength;j++)
            printf("%c",str[j]);
        printf("\n");
    }
    system("pause");
    return 0;
}
void swap(char **a,char **b){
   
    char *temp = *a;
    *a = *b;
    *b = temp;   
}
               
               
               
               
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/82750/showart_2092999.html