poj 1007 DNA Sorting【逆序对】

终于可以说：没有那么水了（虽然还是很水）。。。。。。

关于逆序数的题目，开始用塑料的冒泡排序一直WA，后来自己写一个，终于过了，要求是稳定的！！！！！！！

AC的代码：

#include <stdio.h>
#include <string.h>char DNA[105][55];		//输入原DNA序列
int visit[105];int Inversion(int nTh,int len)
{int i,j,count=0;for(i=0;i<len;i++)for(j=i;j<len;j++)if(DNA[nTh][i]>DNA[nTh][j])count++;return count;
}int main()
{//1A，2B, 3C, 4D, 5E, 6F, 7G, 8H, 9I, 10J, 11K, 12L, 13M, 14N, 15O, 16P, 17Q, 18R, 19S, 20T, 21U, 22V, 23W, 24X, 25Y, 26Zint inverNum[102];		//对应每个数列的逆序数int n;int m;scanf("%d%d",&n,&m);int i,j;for(i=0;i<m;i++){scanf("%s",DNA[i]);inverNum[i]=Inversion(i,n);		//传入排位第i个的DNA序列，和序列长度//test  OK//printf("逆序数为：%d\n",inverNum[i]);}//每次都找到inverNum最小的序列打印，一定是稳定的int min;int pos;for(i=0;i<m;i++){min=1000;	//开始放min为一个很大的数for(j=0;j<m;j++)if(visit[j]==0 && min>inverNum[j]){min=inverNum[j];pos=j;}visit[pos]=1;	//标记被访问过了printf("%s\n",DNA[pos]);}return 0;
}

WA 2次的代码：

#include <stdio.h>
#include <string.h>char DNA[105][55];		//输入原DNA序列int Inversion(int nTh,int len)
{int i,j,count=0;for(i=0;i<len;i++)for(j=i;j<len;j++)if(DNA[nTh][i]>DNA[nTh][j])count++;return count;
}int main()
{//1A，2B, 3C, 4D, 5E, 6F, 7G, 8H, 9I, 10J, 11K, 12L, 13M, 14N, 15O, 16P, 17Q, 18R, 19S, 20T, 21U, 22V, 23W, 24X, 25Y, 26Zint inverNum[102];		//对应每个数列的逆序数int n;int m;scanf("%d%d",&n,&m);int i,j;for(i=0;i<m;i++){scanf("%s",DNA[i]);inverNum[i]=Inversion(i,n);		//传入排位第i个的DNA序列，和序列长度//test  OK//printf("逆序数为：%d\n",inverNum[i]);}//直接用冒泡排序（稳定的）char tmpN,temp[55];for(i=0;i<m;i++)for(j=i;j<m;j++)if(inverNum[i]>=inverNum[j]){//交换逆序数tmpN=inverNum[j];inverNum[j]=inverNum[i];inverNum[i]=tmpN;//交换DNA序列strcpy(temp,DNA[j]);strcpy(DNA[j],DNA[i]);strcpy(DNA[i],temp);}for(i=0;i<m;i++)printf("%s\n",DNA[i]);return 0;
}

中文题目：

题目大意：

     序列“未排序程度”的一个计算方式是元素乱序的元素对个数。例如：在单词序列“DAABEC'”中，因为D大于右边四个单词，E大于C，所以计算结果为5。这种计算方法称为序列的逆序数。序列“AACEDGG”逆序数为1（E与D）——近似排序，而序列``ZWQM'' 逆序数为6（它是已排序序列的反序）。

     你的任务是分类DNA字符串（只有ACGT四个字符）。但是你分类它们的方法不是字典序，而是逆序数，排序程度从好到差。所有字符串长度相同。

输入：

第一行包含两个数：一个正整数n（0<n<=50）表示字符串长度，一个正整数m（0<m<=100）表示字符串个数。接下来m行，每行一个长度为n的字符串。

输出：

输出输入字符串列表，按排序程度从好到差。如果逆序数相同，就原来顺序输出。

样例输入：

10 6

AACATGAAGG

TTTTGGCCAA

TTTGGCCAAA

GATCAGATTT

CCCGGGGGGA

ATCGATGCAT

 

样例输出:

CCCGGGGGGA

AACATGAAGG

GATCAGATTT

ATCGATGCAT

TTTTGGCCAA

TTTGGCCAAA

大致题意：

输入m个长度为n的DNA序列，把他们按照逆序数从小到大稳定排序输出。

PS:“稳定排序”就是当序列中出现A1==A2时，排序前后A1与A2的相对位置不发生改变。