poj1007 DNA sorting

这题目比较简单，看题干就能看出来。求逆序数，我用的是O(n^2)的算法，数据也不大，水过。

也可以用归并排序来做。

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 struct node{
 5     char str[100];
 6     int cnt;
 7     int num;
 8 }str[110];
 9 bool cmp(node a,node b){
10     if(a.cnt==b.cnt) return a.num<b.num;
11     return a.cnt<b.cnt;
12 }
13 int main(){
14     int i,j,cnt;
15     int cas;
16     int n,m;
17     while(~scanf("%d%d",&n,&m)){
18         for(cas=0;cas<m;++cas){
19             scanf("%s",str[cas].str);
20             str[cas].cnt=0;
21             str[cas].num=cas;
22             for(i=0;i<n;++i){
23                 for(j=i+1;j<n;++j){
24                     if(str[cas].str[i]>str[cas].str[j])
25                         str[cas].cnt++;
26                 }
27             }
28         }
29         std::sort(str,str+m,cmp);
30         for(cas=0;cas<m;++cas){
31             printf("%s
",str[cas].str);
32         }
33     }
34     return 0;
35 }