加载中...

POJ 1007 - DNA Sorting


问题描述

输入 m 个长度为 n 的 DNA 序列,把他们按照逆序数从小到大稳定排序输出。

“稳定排序” 就是当序列中出现 A1 == A2 时,排序前后 A1 与 A2 的相对位置不发生改变。

解题思路

没难度,先求各个字符串的逆序数,再按逆序数对字符串快排,用 qsort() 函数。

虽然快排不是稳定的排序,但是只要在定义排序规则函数 cmp 做适当处理,a == b 时返回 0,即不处理 a 和 b,就不会改变他们之间的相对位置了。

AC 源码

//Memory Time 
//252K   16MS 

#include<iostream>
#include<algorithm>
using namespace std;

typedef class dna
{
    public:
        int num;  //逆序数
        char sq[110];  //DNA序列
}DNAStr;

int InversionNumber(char* s,int len)
{
    int ans=0;  //s逆序数
    int A,C,G;  //各个字母出现次数,T是最大的,无需计算T出现次数
    A=C=G=0;
    for(int i=len-1;i>=0;i--)
    {
        switch(s[i])
        {
            case 'A':A++;break;  //A是最小的,无逆序数
            case 'C':
                 {
                     C++;
                     ans+=A;  //当前C后面出现A的次数就是这个C的逆序数
                     break;
                 }
            case 'G':
                {
                    G++;
                    ans+=A;
                    ans+=C;
                    break;
                }
            case 'T':
                {
                    ans+=A;
                    ans+=C;
                    ans+=G;
                    break;
                }
        }
    }
    return ans;
}

int cmp(const void* a,const void* b)
{
    DNAStr* x=(DNAStr*)a;
    DNAStr* y=(DNAStr*)b;
    return (x->num)-(y->num);
}

int main(void)
{
    int n,m;
    while(cin>>n>>m)
    {
        DNAStr* DNA=new DNAStr[m];
        for(int i=0;i<m;i++)
        {
            cin>>DNA[i].sq;
            DNA[i].num = InversionNumber(DNA[i].sq,n);
        }
        qsort(DNA,m,sizeof(DNAStr),cmp);
        for(int j=0;j<m;j++)
            cout<<DNA[j].sq<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录