总时间限制: 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感觉没什么好说的……我的思路是记录下每个DNA的逆序对数，最后用sort进行结构体排序
#include <iostream> #include <string> #include <algorithm> using namespace std; struct Dna{ string str; int num; }; bool cmp(Dna a, Dna b){ return a.num < b.num; } Dna dna[110]; int main(){ int n,m; cin>>n>>m;//字符串长度，字符串数量 for(int i = 0; i < m; i++){ dna[i].num = 0; cin>>dna[i].str; for(int j = 0; j < n - 1; j++){ for(int k = j + 1; k < n; k++){ if(dna[i].str[j] > dna[i].str[k]) dna[i].num++; } // cout<<dna[i].num; } } sort(dna, dna + m, cmp); for(int i = 0; i < m; i++){ cout<<dna[i].str<<endl; } return 0; }