Poj 1007 Java DNA 排序

题目大意：

序列“未排序程度”的一个计算方式是元素乱序的元素对个数。例如：在单词序列“DAABEC’”中，因为D大于右边四个单词，E大于C，所以计算结果为5。这种计算方法称为序列的逆序数。序列“AACEDGG”逆序数为1（E与D）——近似排序，而序列“ZWQM” 逆序数为6（它是已排序序列的反序）。

你的任务是分类DNA字符串（只有ACGT四个字符）。但是你分类它们的方法不是字典序，而是逆序数，排序程度从好到差。所有字符串长度相同。

输入：

第一行包含两个数：一个正整数n（0<n<=50）表示字符串长度，一个正整数m（0<m<=100）表示字符串个数。接下来m行，每行一个长度为n的字符串。

输出：

输出输入字符串列表，按排序程度从好到差。如果逆序数相同，就原来顺序输出。

Java源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.ArrayList;  
import java.util.Collections;  
import java.util.Iterator;  
import java.util.List;  
import java.util.Scanner;  
 
class Main {  
 
    static class Node implements Comparable{  
 
        String str="";  
        int id=0;  
        int sortN=0;  
         
        Node(String str,int id,int sortN){  
            this.str=str;  
            this.id=id;  
            this.sortN=sortN;  
        }  
         
        public int compareTo(Object o) {  
            Node node=(Node)o;  
            if(node.sortN==sortN){  
                return node.id<id?1:(node.id==id?0:-1);  
            }else{  
                return node.sortN<sortN?1:-1;  
            }  
        }  
         
    }  
     
    private static int getSortN(String str){  
        int len=str.length();  
        int ans=0;  
        for(int i=0;i<len;i++){  
            for(int j=i+1;j<len;j++){  
                if(str.charAt(i)>str.charAt(j))  
                    ans++;  
            }  
        }  
        return ans;  
    }  
     
    public static void main(String[] args) {  
        Scanner in = new Scanner(System.in);  
        in.nextInt();  
        int ncase=in.nextInt();  
        List<Node> l=new ArrayList<Node>();  
        for(int i=0;i<ncase;i++){  
            String str=in.next();  
            l.add(new Node(str,i,getSortN(str)));  
        }  
        Collections.sort(l);  
        for(Iterator<Node> it=l.iterator();it.hasNext();){  
            System.out.println(it.next().str);  
        }  
    }  
}

除非注明，饮水思源博客文章均为原创，转载请以链接形式标明本文地址

本文地址： http://www.alonemonkey.com/acmpoj1007.html

本文链接：http://www.alonemonkey.com/acmpoj1007.html