题目描述

逆序对的定义如下:
有一个数列an，对于任意的ai<aj若i>j，则称（ai,aj）为一个逆序对。
我们定义一个序列的无序度为其中的逆序对个数。
我们知道对于DNA，仅仅含有ACGT四种碱基，现在我们定义A

输入

第一行两个整数L和n。
接下来有n行，每一行有一个长度为L的字符串。

输出

n行，每行一个长度为L的字符串。

思路

因为数据不大，可以直接暴力枚举。。

#include 
#include 
using namespace std;
int a[1000],d[1000],f[20000],o[1000][20000];
char s[1000];

int main()
{
    freopen("dna.in", "r", stdin);
    freopen("dna.out", "w", stdout);
    int n,c,len,m,nn;
    scanf("%d%d",&n,&m);
    nn=n;
    for (int k=1;k<=m;k++)
    {
        scanf("%s",&s);
        int x=0;
        for (int j=0;j<=n-1;j++)
        {   
            x++;
            a[x]=s[j]-64;
        }
        for (int i=1;i<=n;i++)
            o[i][k]=a[i];
        len=0;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
            {
                if (a[i]>a[j]&&j>i)
                {
                    len++;
                }
            }
        f[k]=len;
    }

    n=nn;   
    for (int i=1;i<=m;i++)
    {
        int min=0x7fffffff;
        int x=0;
        for (int j=1;j<=m;j++)
        {
            if (min>f[j])
            {
                min=f[j];
                x=j;
            }
        }
        f[x]=0x7fffffff;

        for (int j=1;j<=n;j++)
        {
            if (o[j][x]==1) printf("A");
            if (o[j][x]==3) printf("C");
            if (o[j][x]==7) printf("G");
            if (o[j][x]==20) printf("T");
        }
        printf("\n");
    }
}