POJ1007--DNA Sorting

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
struct e
{
    char a[200];
    int id;
    int px;
}s[200];
int  cmp(e s1,e s2)
{
    if(s1.px==s2.px) return s1.id<s2.id;
    else return s1.px<s2.px;
}


int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
{

    for(int i=0;i<m;i++)
        {   int sum=0;
            s[i].id=i;
            scanf("%s",s[i].a);
            for(int j=0;j<n-1;j++)
            for(int k=j+1;k<n;k++)
                if(s[i].a[j]>s[i].a[k])sum++;
            s[i].px=sum;
        }
        sort(s,s+m,cmp);

        for(int i=0;i<m;i++)
            printf("%s\n",s[i].a);

}
}

但是这种方法获得sum效率不是很高

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
struct e
{
    char a[200];
    int id;
    int px;
}s[200];
int  cmp(e s1,e s2)
{
    if(s1.px==s2.px) return s1.id<s2.id;
    else return s1.px<s2.px;
}

int get(char a[])
{
    int ans = 0;
    int A, C, G;
    A = C = G = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        switch (a[i]) {
            case 'A':
                A++;
                break;
            case 'C':
                C++;
                ans += A;
                break;
            case 'G':
                G++;
                ans += A;
                ans += C;
                break;
            case 'T':
                ans += A;
                ans += C;
                ans += G;
        }
    }
    return ans;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
{

    for(int i=0;i<m;i++)
        {   int sum=0;
            s[i].id=i;
            scanf("%s",s[i].a);
            s[i].px=get(s[i].a);
        }
        sort(s,s+m,cmp);

        for(int i=0;i<m;i++)
            printf("%s\n",s[i].a);

}
}

时间复杂度更低

POJ1007--DNA Sorting

原文：http://blog.csdn.net/hy1405430407/article/details/45032755