UVa 612 DNA Sorting

题目描述序列中的“无序度”可以用逆序对的数量来衡量。例如字母序列DAABEC中D大于其右侧的四个字母E大于其右侧的一个字母因此逆序数为555。序列AACEDGG仅有一个逆序对E和D几乎有序而ZWQM有666个逆序对是完全逆序的。你需要对一组DNA\texttt{DNA}DNA字符串仅包含A、C、G、T四种字符进行排序但不是按字母顺序而是按“有序程度”从“最有序”到“最无序”排列。所有字符串长度相同。若两个字符串逆序数相同则保持它们在输入中的相对顺序。输入格式第一行为一个整数MMM表示数据集的个数。接下来每个数据集的第一行包含两个整数nnn0n≤500 n \le 500n≤50表示字符串长度mmm0m≤1000 m \le 1000m≤100表示字符串个数。随后mmm行每行一个长度为nnn的字符串仅含A、C、G、T。不同数据集之间可能存在空行但cin可以忽略空白字符。输出格式对于每个数据集输出mmm行每行一个字符串按逆序数从小到大排列。若逆序数相同保持输入顺序。不同数据集的输出之间用一个空行分隔。样例输入1 10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT输出CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA题目分析本题的核心是计算每个字符串的逆序数并按逆序数升序排序。逆序数的定义在一个序列中如果一对字符iji jij但sisjs_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−1jjj从i1i1i1到n−1n-1n−1若line[j] line[i]则逆序数加111。将字符串和其逆序数存入结构体数组。使用stable_sort按逆序数升序排序。按排序后的顺序输出字符串。若非最后一个数据集输出一个空行即相邻数据集间空行。复杂度分析每个字符串计算逆序数O(n2)O(n^2)O(n2)n≤50n \le 50n≤50常数很小。排序O(mlog⁡m)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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structitem{string dna;intinversion;booloperator(constitemanother)const{returninversionanother.inversion;}};intgetInversion(stringline){intinversion0;for(inti0;iline.length();i)for(intji1;jline.length();j)if(line[j]line[i])inversion;returninversion;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0,n,m;cincases;vectoritemdnas;for(intc1;ccases;c){dnas.clear();if(c1)cout\n;cinnm;cin.ignore(1024,\n);string line;for(inti0;im;i){getline(cin,line);dnas.push_back((item){line,getInversion(line)});}stable_sort(dnas.begin(),dnas.end());for(autodata:dnas)coutdata.dna\n;}return0;}总结本题是一个典型的排序应用题核心在于正确计算逆序数并利用稳定排序保证相同逆序数的字符串保持原顺序。由于数据规模极小直接暴力计算即可。该题也提醒我们在排序时若需保持相等元素的原始顺序应当使用稳定排序算法如stable_sort而不是普通sort。此解法简洁高效适合作为入门级排序与模拟练习题。