学步园

POJ   1007   DNA Sorting                   题目链接：http://poj.org/problem?id=1007

题目大意：给出一些DNA字符串（仅含AGCT），由逆序数给出排序程度定义（逆序数越大排序程度越低），要求按排序程度递减输出这些DNA串。

题目分析：知道逆序数的知识后还是很容易的…

code:

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
	char c[60];
	int v;
}a[120];
int cmp(node a,node b)
{
	return a.v<b.v;
}
int main()
{
	int i,j,m,n,t,gt,cgt;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%s",a[i].c);
		t=gt=cgt=0;
		for(j=1;j<n;j++)
		{
			switch(a[i].c[j-1])
			{
				case'T':t++;
				case'G':gt++;
				case'C':cgt++;
			}
			switch(a[i].c[j])
			{
				case'A':a[i].v+=cgt;break;
				case'C':a[i].v+=gt;break;
				case'G':a[i].v+=t;
			}
		}
	}
	sort(a,a+m,cmp);
	for(i=0;i<m;i++)
	{
		printf("%s\n",a[i].c);
	}
	return 0;
}

PS：正式开工第一天，逆序数的知识还是比较重要的…