这个题目其实是一个求“逆序数”和排序的题目。逆序数这个东西在线性代数里有，和那个求行列式的时候学到的逆序数其实是一个东西。排序的话，标准库里有，所以这个题目还算是比较水的一道题。

原题地址：http://poj.org/problem?id=1007

问题描述

一种衡量序列的“乱序程度 (unsortedness)”的指标，是序列的“逆序数”（the number of pairs of entries that are out of order with respect to each other, 即序列中所有满足条件的数对的对数，这个条件是：该数对的两个数与整个序列的预期排序不符。）。例如，在“DAABEC”中，逆序数是 5, 因为 D 分别大于后面的 4 个字符，且 E 大于后面的一个字符。这就是序列的逆序数 (the number of inversions in the sequence). 序列“AACEDGG”的逆序数是 1, 因为它只有 E 和 D 是无序的——这表明它接近于有序序列——然而序列“ZWQM”的逆序数是 6（它达到了乱序的极致——正好与预期排序完全相反）。

你现在需要排序一连串的 DNA 数据（DNA 中只有 A, T, G 和 C 四个字母）。然而，你不应该以字典序排列它，而是应该以“排序程度”排列它们，最先输出的是“最排好序的”，最后输出的是“最乱序的”。所有的 DNA 字符串都是相同长度的。

输入

第一行包含两个整数：一个正整数 n (0 < n ≤ 50), 表示每个字符串的长度；另一个整数 m (0 < m ≤ 100), 表示字符串的个数。接下来的 m 行，每行包含一个长度为 n 的字符串。

输出

输出重排后的字符串，从“最排好序的”到“最乱序的”。如果两个字符串的逆序数是一样的，它们应该按照原始的顺序输出。

样例输入

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

样例输出

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

解题思路

先计算每个序列的逆序数，再以此排序。注意不要排序字符串本身，而是排序它们的指针或下标，这样可以减少交换时的开销。并且标准库里的排序函数并不一定是稳定的，所以在所谓的比较函数里，应该在两个字符串逆序数相等的情况下，再比较它们的下标。

源代码

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
import java.util.*;

public class Main {

    static class DNA implements Comparable<DNA> {

        private String chain;
        private int inversion;

        public DNA(String str) {
            inversion = 0;
            chain = str;
            for (int i = 0; i < chain.length(); ++i) {
                for (int j = i + 1; j < chain.length(); ++j) {
                    if (chain.charAt(i) > chain.charAt(j))
                        ++inversion;
                }
            }
        }

        @Override
        public int compareTo(DNA foo) {
            return inversion - foo.inversion;
        }

        @Override
        public String toString() {
            return chain;
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        cin.nextInt(); // Skip the length of string.
        int count = cin.nextInt();
        cin.nextLine(); // Skip \n.

        DNA[] dna = new DNA[count];
        for (int i = 0; i < count; ++i)
            dna[i] = new DNA(cin.nextLine());
        Arrays.sort(dna);

        for (int i = 0; i < count; ++i)
            System.out.println(dna[i]);
    }
}

原创文章，转载请注明来源：http://euyuil.com/2339/poj-1007-dna-sorting/