Description
逆序数可以用来是描述一个序列混乱成度的量。例如，“DAABEC”的逆序数为5，其中D大于它右边的4个数，E大于它右边的1个数，4+1=5；又例如“ZWQM”的逆序数为3+2+1+0=6。
现在有许多长度一样的字符串，每个字符串里面只会出现四种字母（A,T,G,C）。你现在被要求编写程序将这些字符串按照他们的逆序数进行排序
Input
第一行包括两个正整数，第一个正整数N给出了字符串的长度，第二个正整数M给出了字符串的数量。（1<=N，M<=100）
接下来M行每行一个长度为N的字符串，只包含A,T,G,C四种字母。
Output
将输入的字符串按照其逆序数进行排序，如果两个字符串的逆序数相等，则按照输入中两者的先后顺序进行排列。
Sample Input
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
Sample Output
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
Hint
选择排序是不稳定的
Source
HRBEU
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eps 1e-9
const int inf =
0x3f3f3f3f;
const int mod = 1e9+
7;
const int maxn =
100000 +
8;
int n, m;
char c[
1000 +
8][
1000 +
8];
struct node
{
char c[
1000 +
8];
int num, id;
}a[1000 +
8];
bool cmp(node a, node b)
{
if(a.num !=
b.num)
return a.num <
b.num;
return a.id <
b.id;
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>
m;
for(
int i =
0; i < m; i++
)
{
a[i].num =
0;
for(
int j =
0; j < n; j++
)
{
cin>>
c[i][j];
a[i].c[j] =
c[i][j];
a[i].id =
i;
}
}
for(
int i =
0; i < m ; i++
)
for(
int j =
0; j < n -
1; j++
)
for(
int k = j +
1; k < n; k++
)
if(c[i][j] >
c[i][k])
a[i].num++
;
sort(a, a +
m, cmp);
for(
int i =
0; i < m; i++
)
{
for(
int j =
0; j < n; j++
)
cout<<
a[i].c[j];
cout<<
'\n';
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11420744.html
相关资源：JAVA上百实例源码以及开源项目
