DNA排序

2024-08-21 14:58

文章标签 dna 排序

本文主要是介绍DNA排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目直接暴力，但是考察了稳定排序和非稳定排序，使用sort直接WA了（不稳定排序），而使用stable_sort就过了（稳定排序）

[cpp]  view plain copy print ?  
 #include<iostream>  
 #include<algorithm>  
 #include<cstring>  
 #include<cstdio>  
   
 using namespace std;  
   
 const int maxn = 1005;  
 int n;  
   
 struct node{  
     char str[ maxn ];  
     int val;  
     bool operator< ( const node &a )const{  
         return val < a.val;  
     }  
 }edge[ maxn ];  
   
 void Deal( int k ){  
     //cout << len << endl;  
     int sum = 0;  
     //cout << edge[ k ].str << endl;  
     //cout << n << endl;  
     for( int i = 0; i < n; ++i ){  
         for( int j = i + 1; j < n; ++j ){  
             if( edge[ k ].str[ i ] > edge[ k ].str[ j ] ){  
                 sum++;  
                 //cout << "aaaaaaaaaaaaaaaa" << endl;  
             }  
   
         }         
     }  
     edge[ k ].val = sum;  
 }  
   
 int main(){  
     int  m;  
     while( scanf( "%d%d", &n, &m ) != EOF ){  
         for( int i = 0; i < m; ++i ){  
             for( int j = 0; j < n; ++j ){  
                 cin >> edge[ i ].str[ j ];  
             }  
             //getchar();  
             edge[ i ].val = 0;  
             Deal( i );  
             //cout << edge[ i ].val << endl;  
         }  
         stable_sort( edge, edge + m );  
         for( int i = 0; i < m; ++i )  
             cout << edge[ i ].str << endl;  
         puts( "********************");  
     }  
 }  