poj1007-蒲公英云

poj1007

1**．链接地址**

https://vjudge.net/problem/POJ-1007

2**．问题描述**

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.

输入样例

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

输出样例

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

3**．解题思路**

对每个序列求其中逆序数然后排序即可

4**．算法实现源代码**

#include <iostream>
#include <algorithm>
using namespace std;
struct Str
{
    char s[51];
    int n;  
};
bool cmp(const Str &a,const Str &b)
{
    if(a.n<b.n)
        return 1;
    return 0;
}
int main()
{
    int n,m,i,j;
    Str str[101];
    while(cin>>n>>m)
    {
        for(i=1;i<=m;i++)   
            cin>>str[i].s;
        for(i=1;i<=m;i++)
        {
            int num=0;
            int A=0,C=0,G=0;
            for(j=n-1;j>=0;j--)
            {
                switch(str[i].s[j])
                {    
                    case 'A':A++;break;
                    case 'C':C++;num+=A;break;
                    case 'G':G++;num+=A;num+=C;break;
                    case 'T':num+=A;num+=C;num+=G;break;
                    default:break;
                }
            }
            str[i].n = num;
        }
        sort(str+1,str+m+1,cmp);
        for(i=1;i<=m;i++)
            cout<<str[i].s<<endl;
    }
    return 0;
}