本文主要是介绍POJ 1007 DNA 排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：分类DNA字符串（只有ACGT四个字符）。但是分类它们的方法不是字典序，而是逆序数，排序程度从好到差。所有字符串长度相同。
解题思路：第一感觉就是用结构体数组，结构体中存字符数组和这个字符数组的逆序数。然后用两个for循环求逆序数即可。刚开始编完提交WA，仔细看题目才记得是稳定排序，所以把sort改为stable_sort即可实现稳定排序。编写一个判断的函数使逆序数从小到大排序，最后从头到尾输出即可。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
struct abc
{
char s[55];
int n;
}a[110];
bool cmp(abc x,abc y)
{
return x.n<y.n;
}
int main()
{
int t,k,i,j,w;
cin>>t>>k;
for(i=0;i<110;i++)
a[i].n=0;
for(i=0;i<k;i++)
{
cin>>a[i].s;
for(j=0;j<t;j++)
for(w=j+1;w<t;w++)
if(a[i].s[j]>a[i].s[w]) a[i].n++;
}
stable_sort(a,a+k,cmp);
for(i=0;i<k;i++)
cout<<a[i].s<<endl;
return 0;
}
这篇关于POJ 1007 DNA 排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
