[算法] POJ1007

浏览数：26 / 时间：2015年06月08日

网址：http://poj.org/problem?id=1007

首先定义一个字符串大小的概念：右边的字母小于前边字母的数量。给定多组字符串，按照大小顺序输出。

用到的方法：

排序算法

首先需要排序，然后对排序后得到的index进行以下的处理

index_1[index[i]]=i;

最终得到输出。

Sample Input

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Sample Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

源代码

#include<stdio.h>
int main()
{
    int column,raw,i,j,k;
    char str[100][100];
    int sort[100];
    int sort_index[100];
    int sort_index1[100];
    scanf("%d %d",&column,&raw);
    getchar();
    for(i=0;i<raw;i++)
    {    
        for(j=0;j<column;j++)
        {
            str[i][j]=getchar();
        }
        getchar();
    }

    for(i=0;i<raw;i++)
    {    sort_index[i]=0;
        sort[i]=0;
        for(j=0;j<column-1;j++)
        {
            for(k=j+1;k<column;k++)
            {
                if(str[i][j]>str[i][k])
                    sort[i]++;    
            }
        }
    }
    
    for(i=0;i<raw-1;i++)
    {    
        for(j=i+1;j<raw;j++)
        {
            if(sort[i]>sort[j])
                sort_index[i]++;
            else
                sort_index[j]++;
        }
    }
    
    for(i=0;i<raw;i++)
    {    
        sort_index1[sort_index[i]]=i;
    }


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

    return 0;
}