UVa 612 DNA Sorting
题目描述
序列中的“无序度”可以用逆序对的数量来衡量。例如，字母序列DAABEC中，D大于其右侧的四个字母，E大于其右侧的一个字母，因此逆序数为555。序列AACEDGG仅有一个逆序对（E和D），几乎有序；而ZWQM有666个逆序对，是完全逆序的。
你需要对一组DNA\texttt{DNA}DNA字符串（仅包含A、C、G、T四种字符）进行排序，但不是按字母顺序，而是按“有序程度”从“最有序”到“最无序”排列。所有字符串长度相同。若两个字符串逆序数相同，则保持它们在输入中的相对顺序。
输入格式
第一行为一个整数MMM，表示数据集的个数。接下来每个数据集的第一行包含两个整数：nnn（0<n≤500 < n \le 500<n≤50）表示字符串长度，mmm（0<m≤1000 < m \le 1000<m≤100）表示字符串个数。随后mmm行，每行一个长度为nnn的字符串（仅含A、C、G、T）。不同数据集之间可能存在空行，但cin可以忽略空白字符。
输出格式
对于每个数据集，输出mmm行，每行一个字符串，按逆序数从小到大排列。若逆序数相同，保持输入顺序。不同数据集的输出之间用一个空行分隔。
样例
输入
1 10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT输出
CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA题目分析
本题的核心是计算每个字符串的逆序数，并按逆序数升序排序。逆序数的定义：在一个序列中，如果一对字符i<ji < ji<j但si>sjs_i > s_jsi>sj（按字符ASCII\texttt{ASCII}ASCII码大小比较），则构成一个逆序对。由于字符串长度n≤50n \le 50n≤50，直接使用两层循环枚举所有字符对即可在O(n2)O(n^2)O(n2)时间内算出逆序数，总复杂度O(m⋅n2)O(m \cdot n^2)O(m⋅n2)，完全可行。
排序时需要保持逆序数相同元素的原始顺序，因此应使用稳定排序算法（如stable_sort）。这与样例中逆序数相同的字符串保持原输入顺序的要求一致。
解题思路
- 读入MMM表示数据集个数。
- 对于每个数据集：
- 读入nnn和mmm。
- 循环mmm次，读入每个字符串。
- 对每个字符串，通过两层循环统计逆序数：对于iii从000到n−1n-1n−1，jjj从i+1i+1i+1到n−1n-1n−1，若
line[j] < line[i]，则逆序数加111。 - 将字符串和其逆序数存入结构体数组。
- 使用
stable_sort按逆序数升序排序。 - 按排序后的顺序输出字符串。
- 若非最后一个数据集，输出一个空行（即相邻数据集间空行）。
复杂度分析
- 每个字符串计算逆序数：O(n2)O(n^2)O(n2)，n≤50n \le 50n≤50，常数很小。
- 排序：O(mlogm)O(m \log m)O(mlogm)，m≤100m \le 100m≤100。
- 总时间复杂度：O(M⋅m⋅n2)O(M \cdot m \cdot n^2)O(M⋅m⋅n2)，MMM未知但通常较小，完全可接受。
- 空间复杂度：O(m)O(m)O(m)，用于存储字符串和逆序数。
代码实现
// DNA Sorting// UVa ID: 612// Verdict: Accepted// Submission Date: 2016-08-23// UVa Run Time: 0.030s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structitem{string dna;intinversion;booloperator<(constitem&another)const{returninversion<another.inversion;}};intgetInversion(string&line){intinversion=0;for(inti=0;i<line.length();i++)for(intj=i+1;j<line.length();j++)if(line[j]<line[i])inversion++;returninversion;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0,n,m;cin>>cases;vector<item>dnas;for(intc=1;c<=cases;c++){dnas.clear();if(c>1)cout<<'\n';cin>>n>>m;cin.ignore(1024,'\n');string line;for(inti=0;i<m;i++){getline(cin,line);dnas.push_back((item){line,getInversion(line)});}stable_sort(dnas.begin(),dnas.end());for(autodata:dnas)cout<<data.dna<<'\n';}return0;}总结
本题是一个典型的排序应用题，核心在于正确计算逆序数并利用稳定排序保证相同逆序数的字符串保持原顺序。由于数据规模极小，直接暴力计算即可。该题也提醒我们，在排序时若需保持相等元素的原始顺序，应当使用稳定排序算法（如stable_sort），而不是普通sort。此解法简洁高效，适合作为入门级排序与模拟练习题。