[POJ] DNA Sorting

Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 83069
Accepted: 33428

Description
One measure of unsortedness in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence DAABEC, this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence AACEDGG has only one inversion (E and D)—it is nearly sorted—while the sequence ZWQM has 6 inversions (it is as unsorted as can be—exactly the reverse of sorted).

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of sortedness, from most sorted to least sorted. All the strings are of the same length.

Input
The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

Output
Output the list of input strings, arranged from most sorted'' toleast sorted”. Since two strings can be equally sorted, then output them according to the orginal order.

Sample Input

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Sample Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

Source
East Central North America 1998

解题思路

首先求出逆序数,然后对逆序数进行排队,最后输出排序后的DNA序列。对于求逆序数,只需对序列进行遍历,找出本应出现在某字符之后,却出现在了它之前的字符数即可(顺序为ACGT)。

实现代码

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

typedef struct node
{
    char s[100];
    int value; //逆序对数
}DNA;

bool cmp(DNA d1, DNA d2)
{
    return d1.value < d2.value;
}

//获取逆序对数
int rev_cnt(char *ch)
{
    int cnt[4] = {0};
    int reverse_cnt = 0;
    int i = 0;
    while(ch[i])
    {
        switch(ch[i])
        {
        case 'A':
            cnt[0]++;
            reverse_cnt += cnt[1] + cnt[2] + cnt[3];
            break;
        case 'C':
            cnt[1]++;
            reverse_cnt += cnt[2] + cnt[3];
            break;
        case 'G':
            cnt[2]++;
            reverse_cnt += cnt[3];
            break;
        case 'T':
            cnt[3]++;
            break;
        }
        i++;
    }

    return reverse_cnt;
}

void sort(DNA *d, int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        int index = i;
        for (int j = i + 1; j < len; j++)
        {
            if (d[j].value < d[index].value)
            {
                index = j;
            }
        }

        if (index != i)
        {
            //DNA temp;
            //memcpy(&temp, &d[i], sizeof(d[i]));
            //memcpy(&d[i], &d[index], sizeof(d[index]));
            //memcpy(&d[index], &temp, sizeof(temp));
            DNA temp = d[i];
            d[i] = d[index];
            d[index] = temp;
        }
    }
}

int main()
{
    int m, n;
    scanf("%d%d", &m, &n); //m为输入字符长度,n为数据组数
    DNA *d = new DNA[n];
    int i = 0;
    while(i < n)
    {
        scanf("%s", d[i].s);
        d[i].value = rev_cnt(d[i].s);
        i++;
    }

    sort(d, d + n, cmp);
    //sort(d, n);自定义排序函数
    for (int i = 0; i < n; i++)
    {
        cout<<d[i].s<<endl;
    }

    delete [] d;
    return 0;
}

排序部分可以用<algorithm>里面的sort,也可以是自定义的。输入部分如果将scanf改为cin.getline(d[i].s, m+1)则需要先用一个scanf("%c", &c)读取两个整数之后的回车符。

转载:http://blog.csdn.net/foreverling/article/details/44559603

时间: 2024-10-29 22:22:15

[POJ] DNA Sorting的相关文章

POJ:DNA Sorting 特殊的排序

Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to

poj 1007 DNA Sorting【逆序对】

终于可以说:没有那么水了(虽然还是很水)...... 关于逆序数的题目,开始用塑料的冒泡排序一直WA,后来自己写一个,终于过了,要求是稳定的!!!!!!! AC的代码: #include <stdio.h> #include <string.h> char DNA[105][55]; //输入原DNA序列 int visit[105]; int Inversion(int nTh,int len) { int i,j,count=0; for(i=0;i<len;i++) f

poj 1094 Sorting It All Out(拓扑排序)

链接: http://poj.org/problem?id=1094 题目: Sorting It All Out Time Limit: 1000MS     Memory Limit: 10000K Total Submissions: 21532     Accepted: 7403 Description An ascending sorted sequence of distinct values is one in which some form of a less-than ope

poj 1093 Sorting It All Out AOV网络+拓扑

          一道拓扑的题,只是每增加一条拓扑一次,要注意是否有人为添加的边,也就是同一时刻有没有多个可选项.         这题少加了个return 0,错了n次--注意细节.          非常简单的题,结果写了70多分钟--   /* author:jxy lang:C/C++ university:China,Xidian University **If you need to reprint,please indicate the source** */ #include

POJ题目分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

算法题:poj 3080 Blue Jeans(KMP匹配,枚举子串)

链接: http://poj.org/problem?id=3080 题目大意: 给出m(2<=m<=10)个DNA序列, 求出这m个序列中最长的公共字串.如果有多个相同长度的, 输出字典序最小的. 分析与总结: 依次枚举所有的子串, 然后再看是否在所有序列中都能够匹配.保存下长度最大且字典序最小的序 列. 代码: #include<iostream> #include<cstdio> #include<cstring> using namespace st

poj分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

poj 3080 Blue Jeans

点击打开链接poj 3080 思路:kmp+子串枚举 分析: 1 题目要求的是给定m个DNA序列,每个DNA序列长度固定为60,问m个DNA序列的最长的公共子串 2 初看题目无从下手,但是你仔细研究发现是要找m个序列的公共子串,那么这个子串必定存在于第一个DNA序列里面.这个时候就可以想到去枚举第一个DNA序列的所有子串,由于长度为60那么最多3600个子串,由于m最多10个:所以算一下复杂度就是0(3600*n*m),n是60和m最大10,那么这样的复杂度是可以接受的. 代码: #includ

【算法趣题】产生随机DNA序列(字串)

[题目说明]写一段程序(不限语言),能够按要求产生随机DNA序列(字串). DNA序列由A.T.C.G四种碱基(字符)组成.现要求按A 10%, T 20%, C 30%, G 40% 的比例产生长度为100个碱基的DNA序列. 注意要随机程度好,且符合比例要求. 我先抛砖引玉了:(大家最好先别看我的程序,否则可能会影响你自己的思路) 以下是HTML网页特效代码,点击运行按钮可查看效果: [Ctrl+A 全部选择 提示:你可先修改部分代码,再按运行]