poj1007

深藏阁楼爱情的钟 2021-11-23 15:38 217阅读 0赞

**1****．链接地址**

[https://vjudge.net/problem/POJ-1007][https_vjudge.net_problem_POJ-1007]

**2****．问题描述**

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.

输入样例

10 6
    AACATGAAGG
    TTTTGGCCAA
    TTTGGCCAAA
    GATCAGATTT
    CCCGGGGGGA
    ATCGATGCAT

输出样例

CCCGGGGGGA
    AACATGAAGG
    GATCAGATTT
    ATCGATGCAT
    TTTTGGCCAA
    TTTGGCCAAA

**3****．解题思路**

对每个序列求其中逆序数然后排序即可

**4****．算法实现源代码**

#include <iostream>
    #include <algorithm>
    using namespace std;
    struct Str
    {
        char s[51];
        int n;  
    };
    bool cmp(const Str &a,const Str &b)
    {
        if(a.n<b.n)
            return 1;
        return 0;
    }
    int main()
    {
        int n,m,i,j;
        Str str[101];
        while(cin>>n>>m)
        {
            for(i=1;i<=m;i++)   
                cin>>str[i].s;
            for(i=1;i<=m;i++)
            {
                int num=0;
                int A=0,C=0,G=0;
                for(j=n-1;j>=0;j--)
                {
                    switch(str[i].s[j])
                    {    
                        case 'A':A++;break;
                        case 'C':C++;num+=A;break;
                        case 'G':G++;num+=A;num+=C;break;
                        case 'T':num+=A;num+=C;num+=G;break;
                        default:break;
                    }
                }
                str[i].n = num;
            }
            sort(str+1,str+m+1,cmp);
            for(i=1;i<=m;i++)
                cout<<str[i].s<<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/KasenBob/p/11217496.html

[https_vjudge.net_problem_POJ-1007]: https://vjudge.net/problem/POJ-1007

发表评论取消回复

表情：

评论列表（有 0 条评论，217人围观）

还没有评论，来说两句吧...

相关阅读

相关 1007 级数求和

题目描述 Description 已知：Sn= 1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。　　现给出一个整数K（1<=k<=

秒速五厘米/ 2022年09月28日 13:25/ 0 赞/ 180 阅读

相关 1007 最大乘积

Description 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助

矫情吗；*/ 2022年09月11日 12:25/ 0 赞/ 145 阅读

相关 URAL--1007 codewords

三种信息传递过程中可能出错的方式，让你恢复原来正确的信息。我用的是分类暴搜，用字符串模拟的，这里还是是可行的，不过debug快坑死了o(╯□╰)o...... 后面还有一

落日映苍穹つ/ 2022年08月11日 00:44/ 0 赞/ 169 阅读

相关 POJ1007解题报告

其实就是求线性代数里面所谓的逆序数，既然是逆序数那肯定从后往前计数，通过计算每个字符的逆序数最终算出整个字符串的逆序数。用switch进行条件判断，比如CAGT，直观上看这

素颜马尾好姑娘i/ 2022年08月10日 20:00/ 0 赞/ 306 阅读

相关 POJ 1007 DNA Sorting

DNA Sorting Description One measure of ”unsortedness” in a sequence is the number of

约定不等于承诺〃/ 2022年06月17日 00:38/ 0 赞/ 155 阅读

相关 P1007 独木桥

题目背景战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景

傷城~/ 2022年06月16日 07:16/ 0 赞/ 128 阅读

相关 JOJ 1007解题

![art.gif][] [1007][]: Triangles -------------------- <table style="font-family:Verd

阳光穿透心脏的1/2处/ 2022年06月08日 07:18/ 0 赞/ 205 阅读

相关 PAT乙级1007

1007 素数对猜想（20 分）让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻

缺乏、安全感/ 2022年05月16日 03:57/ 0 赞/ 167 阅读

相关 poj1007

1．链接地址 [https://vjudge.net/problem/POJ-1007][https_vjudge.net_problem_POJ-1007] 2．问题描述

深藏阁楼爱情的钟/ 2021年11月23日 15:38/ 0 赞/ 218 阅读

相关【洛谷 1007】独木桥

题目背景战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景

今天药忘吃喽~/ 2021年10月24日 04:56/ 0 赞/ 296 阅读