1007

总时间限制:

1000ms

内存限制:

65536kB

描述

现在有一些长度相等的DNA串（只由ACGT四个字母组成），请将它们按照逆序对的数量多少排序。

逆序对指的是字符串A中的两个字符A[i]、A[j]，具有i < j 且 A[i] > A[j] 的性质。如字符串”ATCG“中，T和C是一个逆序对，T和G是另一个逆序对，这个字符串的逆序对数为2。

 

输入

第1行：两个整数n和m，n(0<n<=50)表示字符串长度，m(0<m<=100)表示字符串数量

第2至m+1行：每行是一个长度为n的字符串

输出

按逆序对数从少到多输出字符串，逆序对数一样多的字符串按照输入的顺序输出。

样例输入

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

样例输出

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

 

解决方案一：G++

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std ;
#define N 51
#define M 101
int main()
{   int count(const char ch[],int len) ;
    void swap(char ch[][N],int a[],int len) ;
    void print(char ch[][N],int len) ;
    char ch[M][N] ;
    int a[M];
    int n,m ;
    cin>>n>>m ;
    for(int i=0;i<m;i++)
        {
            cin>>ch[i];
            int len = strlen(ch[i]) ;
            a[i] = count(ch[i],len) ;
        }
    swap(ch,a,m) ;
    print(ch,m) ;
    return 0 ;
}
int count(const char ch[],int len){
    int k=0;
 for(int i=0;i<len;i++)
 {
     for(int j=i+1;j<len;j++){
     if((ch[j]-ch[i])<0) k++ ;
     }
 }
    return k ;
}
void swap(char ch[][N],int a[],int len)
{
    for(int i=0;i<len;i++){
      int temp = a[i] ;
      char c[51];

        for(int j=i+1;j<len;j++){
           if(a[i]>a[j]){
              temp = a[i] ;
              a[i] = a[j] ;
              a[j] = temp ;
              strcpy(c,ch[i]) ;
              strcpy(ch[i],ch[j]) ;
              strcpy(ch[j],c) ;
           }
        }
    }

}
void print(char ch[][N],int len)
{
    for(int i=0;i<len;i++)
    {
        cout<<ch[i]<<endl ;
    }
}

 

解决方案二： Java

 

package dsa;

import java.util.Scanner;
/**
 * 1007题
 * @author tanlvxu
 *
 */
public class Demo9 {

	public static void main(String[] args) {
		test();

	}
    public static void test()
    {
    	Scanner sc = new Scanner(System.in) ;
		int n = sc.nextInt() ;
		int m = sc.nextInt() ;
		String str[] = new String[m] ;
		int a[] = new int[m] ;
		for(int i=0;i<m;i++)
		{
			str[i] = sc.next() ;
			a[i] = count(str[i]) ;
		}
        swap(str,a) ;
        print(str) ;
        
    }
    /**
     * 记录逆序数
     * @param str
     * @return
     */
    public static int count(String str)
    {    
    	int k = 0 ;
    	for(int i=0;i<str.length();i++)
    	{    
    		for(int j=i+1;j<str.length();j++)
    		{ 
    			if(str.charAt(i)-str.charAt(j)>0)  k++ ;
    			
    		}
    	}
    	return k ;
    }
    /**
     * 输出
     * @param str
     */
    public static void print(String str[])
    {
    	for(int i=0;i<str.length;i++)
    	{    
    		System.out.println(str[i]) ;
    	}
    }
    /**
     * 交换元素
     * @param str
     * @param a
     */
    public static void swap(String str[],int a[])
    {
    	for(int i=0;i<str.length;i++)
    	{    
    		int temp = a[i] ;
    		String s ;
    		for(int j=i+1;j<str.length;j++)
    		{ 
    			if(a[i]>a[j]){
    	              temp = a[i] ;
    	              a[i] = a[j] ;
    	              a[j] = temp ;
    	           s =  str[i]  ;
    	           str[i] = str[j] ;
    	           str[j] = s ;
    	           }

    			
    		}
    	}
    }
}