【poj1007】 DNA Sorting

时间：2021-02-24 05:51:00

http://poj.org/problem?id=1007 (题目链接)

题意

　　给出m个字符串，将其按照逆序对个数递增输出。

Solution

　　树状数组经典应用。

代码

// poj1007

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<string>

#include<map>

#define MOD 1000000007

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    LL x=0,f=1;char ch=getchar();

    while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=200;

struct data {int cnt;char s[110];}a[maxn];

int n,m,c[10];

bool cmp(data a,data b) {return a.cnt<b.cnt;}

int lowbit(int x) {return x&-x;}

void add(int x) {

    for (int i=x;i<=4;i+=lowbit(i)) c[i]++;

}

int query(int x) {

    int s=0;

    for (int i=x;i>=1;i-=lowbit(i)) s+=c[i];

    return s;

}

int main() {

    scanf("%d%d",&n,&m);

    for (int i=1;i<=m;i++) scanf("%s",a[i].s);

    for (int i=1;i<=m;i++) {

        for (int j=0;j<=5;j++) c[j]=0;

        for (int j=n-1;j>=0;j--) {

            int x;

            if (a[i].s[j]=='A') x=1;

            else if (a[i].s[j]=='C') x=2;

            else if (a[i].s[j]=='G') x=3;

            else x=4;

            add(x);

            if (x>1) a[i].cnt+=query(x-1);

        }

    }

    sort(a+1,a+1+m,cmp);

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

    return 0;

}

　　

相关文章