|
题意：分类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;
}
| 
转播
