求dna的无序的数值（dna sorting）.cpp

北京大学ACM练习网站1007题

#include<iostream>
#include<string>
using namespace std;
void change(int** A,int*B,string strs[],int n,int m){
	int i,j,k;
	string str;
	for(k=0;k<m;k++){
		for(i=0;i<n;i++)for(j=0;j<4;j++)A[i][j]=0;
		str=strs[k];
		if(str.substr(n-1,1).compare("A")==0)A[n-1][0]=1;
		else if(str.substr(n-1,1).compare("C")==0)A[n-1][1]=1;
		else if(str.substr(n-1,1).compare("G")==0)A[n-1][2]=1;
		else if(str.substr(n-1,1).compare("T")==0)A[n-1][3]=1;
    	for(i=n-2;i>-1;i--){
			if(str.substr(i,1).compare("A")==0){A[i][0]=1;B[k]+=0;}
			else if(str.substr(i,1).compare("C")==0){A[i][1]=1;B[k]+=A[i+1][0];}
			else if(str.substr(i,1).compare("G")==0){A[i][2]=1;B[k]+=A[i+1][0]+A[i+1][1];}
			else if(str.substr(i,1).compare("T")==0){A[i][3]=1;B[k]+=A[i+1][0]+A[i+1][1]+A[i+1][2];}
			A[i][0]+=A[i+1][0];
			A[i][1]+=A[i+1][1];
			A[i][2]+=A[i+1][2];
			A[i][3]+=A[i+1][3];
		}
	}
	
}
void mergesort(int A[],int temp[],int f[],int tf[],int left,int right){
	int mid=(left+right)/2;
	if(left==right)return;
	mergesort(A,temp,f,tf,left,mid);
	mergesort(A,temp,f,tf,mid+1,right);
	for(int i=left;i<=right;i++){temp[i]=A[i];tf[i]=f[i];}
	int i1=left;int i2=mid+1;
	for(int curr=left;curr<=right;curr++){
		if(i1==mid+1){
			A[curr]=temp[i2++];
			f[curr]=tf[i2-1];
		}
		else if(i2>right){
			A[curr]=temp[i1++];
			f[curr]=tf[i1-1];
		}
		else if(temp[i1]<temp[i2]){
			A[curr]=temp[i1++];
			f[curr]=tf[i1-1];
		}
		else {
			A[curr]=temp[i2++];
			f[curr]=tf[i2-1];
		}
	}
}

int main(){
	string strs[100],str2[100];
	int**A,B[100],C[100],f[100],tf[100],i,n,m;
	A=new int*[100];
	for(i=0;i<50;i++)A[i]=new int[4];
	for(i=0;i<100;i++){B[i]=0;f[i]=i;}
	n=10;
	m=6;
	cin>>n>>m;
	for(i=0;i<m;i++){cin>>strs[i];str2[i]=strs[i];}
/*
	strs[0]="AACATGAAGG";
	strs[1]="TTTTGGCCAA";
	strs[2]="TTTGGCCAAA";
	strs[3]="GATCAGATTT";
	strs[4]="CCCGGGGGGA";
	strs[5]="ATCGATGCAT";
    for(i=0;i<m;i++)str2[i]=strs[i];
*/
	change(A,B,strs,n,m);
	mergesort(B,C,f,tf,0,m-1);
	for(i=0;i<m;i++){
		strs[i]=str2[f[i]];
		cout<<strs[i]<<endl;
	}
	return 0;
}