`

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 ;
    	           }

    			
    		}
    	}
    }
}
 
分享到:
评论

相关推荐

    openwrt HP1007打印插件

    OpenWrt HP1007 打印插件是一个针对OpenWrt开源固件系统设计的专门用于HP LaserJet 1007打印机的软件组件。OpenWrt是一款基于Linux的嵌入式操作系统,广泛应用于路由器和其他网络设备,提供高度自定义和扩展性。这个...

    hp1007 1008原版驱动 越南版驱动.rar

    标题中的“hp1007 1008原版驱动 越南版驱动.rar”指的是惠普(HP)1007和1008型号打印机的专用驱动程序,该版本是针对越南地区的。在IT领域,驱动程序是操作系统与硬件设备之间的重要桥梁,它允许操作系统识别并有效...

    惠普HP LaserJet P1007 打印机驱动.zip

    【惠普HP LaserJet P1007打印机驱动】是一款专为惠普LaserJet P1007黑白激光打印机设计的重要软件组件,它确保了打印机与计算机之间的有效通信,从而实现高质量的打印功能。这款驱动程序是针对Windows操作系统64位...

    1007打印机驱动下载

    标题中的“1007打印机驱动下载”表明我们要讨论的是HP LaserJet P1007打印机的驱动程序,这是HP公司推出的一款适用于个人和小型办公室的黑白激光打印机。这款驱动程序是用户在Windows XP系统上顺利运行打印机所必需...

    pc6-HP LaserJet P1007

    【标题】"pc6-HP LaserJet P1007" 涉及的主要知识点是惠普(HP)LaserJet P1007激光打印机的驱动程序安装。这款打印机是一款经济实惠的个人桌面激光打印机,专为小型办公室或家庭办公环境设计。...

    Zkteco中控智慧信息屏设备ZK-S1007用户手册.pdf

    【Zkteco中控智慧信息屏设备ZK-S1007用户手册】是一份详细的指导文档,旨在帮助用户充分理解和操作中控智慧的ZK-S1007信息屏设备。这款设备集成了先进的生物识别技术和多媒体展示功能,常用于办公、教育、商业等场所...

    Homebus MM1007 datasheet

    Homebus MM1007是日立公司设计的一款符合HBS(Home Bus System)标准的集成电路,主要用于在家庭自动化和通信设备中实现数据的接收和发送。HBS是一种由日本电子工业协会制定的通信协议,它允许不同类型的电子设备...

    CHT 1007-2001 基础地理信息数字产品元数据.zip

    《CHT 1007-2001 基础地理信息数字产品元数据》是中国台湾地区制定的一项标准,旨在规范基础地理信息数字产品的元数据内容和格式,以提高数据的共享与交换效率。元数据是描述数据的数据,包含关于数据集的基本信息,...

    惠普1007打印机驱动

    本文将详细探讨“惠普1007打印机驱动”这一主题,包括其重要性、功能以及如何安装和使用。 首先,我们要明白的是,"HP1007"是一款由惠普公司生产的喷墨式打印机。喷墨打印机因其经济实惠、色彩表现力强等特点,被...

    HP_Laserjet 1007 mac 驱动

    HP Laserjet 1007 驱动 打印机驱动 mac

    amd体质检测工具-amd体质Tool1007.zip

    这个压缩包"amd体质Tool1007.zip"包含了一系列与AMD处理器性能相关的组件和数据文件,可以帮助用户了解他们的AMD处理器在运行中的表现和可能的优化潜力。 首先,我们看到两个CSV文件——"snoop_res_DEC.csv"和...

    CeCabMgr1007.zip

    【标题】"CeCabMgr1007.zip" 指的可能是一个软件或系统更新的压缩包,其中包含了多个组件。"CeCabMgr" 可能是 "Compact CAB Manager" 的缩写,暗示这个包可能与管理和处理CAB( Cabinet)格式的文件有关。CAB文件是...

    惠普p1007打印机驱动程序.rar

    在这个案例中,压缩包文件“HPlaserjetp1007_33LC.com”很可能就是这个驱动程序的安装文件。 2. **解压文件**:下载后,使用解压缩软件(如WinRAR或WinZip)打开并提取文件。如果文件是自解压格式,只需双击运行...

    HP1007 1008打印机驱动

    HP1007和HP1008是惠普公司推出的两款入门级激光打印机,主要面向个人用户和小型办公室。这两款打印机具有小巧的体积、经济的耗材以及较为简单的操作,深受用户喜爱。本文将深入探讨它们的驱动程序及其在安装与使用中...

    惠普HP1007打印机的OPENWRT用的打印驱程,和X86用的驱动

    标题中的“惠普HP1007打印机的OPENWRT用的打印驱程,和X86用的驱动”指的是为惠普HP1007打印机准备的两种不同平台的驱动程序。首先,我们来详细了解这两种驱动以及它们各自适用的环境。 1. OPENWRT驱动: ...

    POJ1007-DNA Sorting

    【标题】"POJ1007-DNA Sorting"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目要求参赛者编写程序,对DNA序列进行排序,具体而言,就是对一系列由ATCG四种碱基组成的DNA字符...

    sihpP1007.dl cups打印服务器

    sihpP1007.dl cups打印服务器

    HP LaserJetP1007.zip

    "HP LaserJetP1007.zip"这个压缩包文件正是为了解决这个问题而存在的。 该压缩包包含的"HP LaserJet_P1000_P1500.exe"和"LaserJet_P1000_Drvsky.exe"是HP LaserJet P1007打印机的驱动程序文件,它们能够帮助用户的...

Global site tag (gtag.js) - Google Analytics