加载中...

POJ 1007 - DNA Sorting

算法

原创

发布日期: 2011-02-25

更新日期: 2024-11-17

文章字数: 495

阅读时长: 2 分

阅读次数:

POJ 1007 - DNA Sorting
Time: 1000MS
Memory: 10000K
难度: 初级
分类: 排序

问题描述

输入 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;
}