POJ1007解题报告

素颜马尾好姑娘i 2022-08-10 20:00 322阅读 0赞

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

比如CAGT，直观上看这个序列的逆序数应该是1。

算法描述为：

首先从T开始，由于T是最‘大’的且是最后一个字符，故其逆序数是0；

然后是G，G<T ，所以G的逆序数是0；

以此类推，A的逆序数是0，C的逆序数是1。

不难发现计算逆序数是一个累加的过程，并且从后往前知道遇到比前一个字符大的字符才把计数加到结果上，比如AAAA的逆序是0。

再比如字串TGCA，当计算C、G、T的逆序数时，都要把A算进去。即他们的你逆序数分别为T3 G2 C1 A0 （字串的逆序数为3+2+1=6）

计算出逆序数对结果排序即可。

代码如下：

/*
    Arthur:	Near_zh
    Date:	2014/08/09
    Note:	Poj1007
    */
    #include <iostream>
    #include <string>
    using namespace std;
    typedef struct  
    {
    	int num;
    	string str;
    }DNA;
    
    int cmp(const void* a,const void* b)  
    {  
        DNA* x=(DNA*)a;  
        DNA* y=(DNA*)b;  
        return (x->num)-(y->num);  
    } 
    void CountInverseNumber(DNA* dna)
    {
    	int i;
    	//DNA*p=dna;
    	int len=dna->str.size();
    	int A=0;
    	int C=0;
    	int G=0;
    	int result=0;
    //	int T;
    	for(i=len-1;i>=0;i--)
    	{
    		switch(dna->str[i])
    		{
    			case 'A':
    				A++;
    				break;
    			case 'C':
    				//A++;
    				C++;
    				result+=A;
    				break;
    			case 'G':
    				G++;
    				result+=A;
    				result+=C;
    				break;
    			case 'T':
    				result+=A;
    				result+=C;
    				result+=G;
    		}			
    	}
    	dna->num=result;
    }
    
    int main()
    {
    	DNA dna[101];
    	int n;
    	int m;
    	int count=0;
    	cin>>n>>m;
    	while(m--)
    	{
    		cin>>dna[count].str;//input
    		count++;
    	}
    	int i;
    	//cout<<"count="<<count<<endl;
    	for(i=0;i<count;i++)
    	{
    		CountInverseNumber(&dna[i]);
    	}
    	qsort(dna,count,sizeof(DNA),cmp);  
    	for(i=0;i<count;i++)
    	{
    		cout<<dna[i].str<<endl;
    	}
    	return 0;
    }