DNA SORT(求逆序数)

  1 #include <iostream>
  2 #include <string.h>
  3 //#include <fstream>
  4 
  5 using namespace std;
  6 
  7 static int ans=0;
  8 
  9 void swap(int& a,int& b)
 10 {
 11     int t;
 12     t=a;
 13     a=b;
 14     b=t;
 15 }
 16 
 17 void swap(char*a ,char*b )
 18 {
 19     char s[55];
 20     strcpy(s,a);
 21     strcpy(a,b);
 22     strcpy(b,s);
 23 }
 24 
 25 int mergesort(char*a,char* t,int x,int y)
 26 {
 27 
 28     if(y-x>1)
 29     {
 30         int m=x+(y-x)/2;
 31         int p=x,i=x,q=m;
 32         mergesort(a,t,x,m);
 33         mergesort(a,t,m,y);
 34 
 35         while(p<m||q<y)
 36         {
 37             if(q>=y||(p<m&&(a[p]<=a[q])))
 38                {
 39                    t[i++]=a[p++];
 40                }
 41             else
 42                 {
 43                     t[i++]=a[q++];
 44                     ans+=m-p;//对于左边每一个数，右边还没来得及复制的数就是对应的逆序数
 45                 }
 46         }
 47 
 48         for(i=x;i<y;i++)
 49         {
 50             a[i]=t[i];
 51         }
 52 
 53     }
 54 
 55     return ans;
 56 }
 57 
 58 
 59 int main()
 60 {
 61     //ifstream fin;
 62     //fin.open("ss.txt");
 63     int n,m;
 64     cin>>n>>m;
 65     char str[105][55];
 66     char t[55];
 67     int c[105]={0};
 68 
 69     for(int i=0;i<m;i++)
 70     {
 71         for(int j=0;j<n;j++)
 72         {
 73             cin>>str[i][j];
 74         }
 75         ans=0;
 76         char s[55];
 77         strcpy(s,str[i]);
 78         c[i]=mergesort(s,t,0,n);
 79     }
 80 
 81     for(int i=m-1;i>0;i--)
 82     {
 83         for(int j=0;j<i;j++)
 84         {
 85             if(c[j]>c[j+1])
 86             {
 87                 swap(c[j],c[j+1]);
 88                 swap(str[j],str[j+1]);
 89             }
 90         }
 91     }
 92 
 93     for(int i=0;i<m;i++)
 94     {
 95       for(int j=0;j<n;j++)
 96         cout<<str[i][j];
 97       cout<<endl;
 98     }
 99 
100     return 0;
101 }