1007 ++.txt

PKU ACM 1007 的源码,求逆序的算法时间复杂度控制在O(n)

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct _DNA{
	char str[50];
	int sorted;
};

int sortdna(char *str, int len)
{
        int i;  
        int cnt = 0;
        int a[4] = {0};
        for(i = len - 1; i >= 0; i--) {
                switch (str[i]) {
                        case 'A':
                                a[1]++; 
                                a[2]++; 
                                a[3]++; 
                                break;  
                        case 'C':
                                a[2]++; 
                                a[3]++; 
                                cnt += a[1];
                                break;  
                        case 'G':
                                a[3]++; 
                                cnt += a[2];
                                break;  
                        case 'T':
                                cnt += a[3];
                }
        }
        return cnt;
}


int cmp(_DNA a,_DNA b){
	return a.sorted<b.sorted;
}

int main(){
	int i,n,m;
	vector<_DNA> dna;
	scanf("%d%d",&m,&n);
	for(i=0;i<n;i++){
		_DNA temp;
		scanf("%s",temp.str);
		temp.sorted=sortdna(temp.str,m);
		dna.push_back(temp);
	}
	sort(dna.begin(),dna.end(),cmp);
	
	for(i=0;i<n;i++) printf("%s\n",dna[i].str);
	return 0;
}