DNA Sorting

题目描述：

Crawling in PRocess...Crawling failedTime Limit:2000MS    Memory Limit:65536KB   64bit IO Format:%lld & %llu

Description

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

InputThe first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (1 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

OutputOutput the list of input strings, arranged from ``most sorted'' to ``least sorted''. If two or more strings are equally sorted, list them in the same order they are in the input file.

Sample Input

1

10 6AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT

Sample OutputCCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAA

简述：

根据每一串字符串的逆序数来进行排序。

解题思路：

首先想到运用刚刚学的结构体来存储字符串然后运用冒泡排序，但发现并不可行，关键是vector容器的选择，另一个就是逆序数的计算。

解题细节：

1.因粗心大意，导致不能AC。

2.可以用sort进行排序，简单快捷.

3.当逆序数相等时，按原先固有位置排序。

代码：

#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;bool comp(const string &s1,const string &s2)//引用两个字符串{    int i,j,k,m,n;    int sum1=0,sum2=0;    for(i=0;i<s1.size();i++)    {        for(j=i+1;j<s1.size();j++)        {        if(s1[i]>s1[j])         sum1++;        }    }    for(i=0;i<s2.size();i++)    {        for(j=i+1;j<s2.size();j++)        {             if(s2[i]>s2[j])            sum2++;        }    }    return sum1!=sum2?sum1<sum2:sum1<sum2;//如果两行字符串逆序数相同，那么按原先固有的位置排序}int main(){    string s;    vector<string>v;//建立向量    int n,a,b;    cin>>n;    int i,j,k;    int p=0;//p来代表块数    for(i=0;i<n;i++)    {        cin.clear();        cin>>a>>b;        v.clear();//清空向量        p++;        for(j=0;j<b;j++)        {            cin>>s;            v.push_back(s);        }        sort(v.begin(),v.end(),comp);//采用sort排序        if(p!=1)        cout<<endl;//不是第一行的时候，产生新的一行        for(k=0;k<v.size();k++)        {        cout<<v[k]<<endl;        }    }    return 0;}
心得：
解题不能过于着急，细心细致。