hdu 1379 DNA Sorting

向右看齐 2022-06-08 04:40 152阅读 0赞

# DNA Sorting #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 3435    Accepted Submission(s): 1661**

Problem Description

One measure of \`\`unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence \`\`DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence \`\`AACEDGG'' has only one inversion (E and D)--it is nearly sorted--while the sequence \`\`ZWQM'' has 6 inversions (it is as unsorted as can be--exactly the reverse of sorted).   
  
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of \`\`sortedness'', from \`\`most sorted'' to \`\`least sorted''. All the strings are of the same length.   
  
  
This problem contains multiple test cases!  
  
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.  
  
The output format consists of N output blocks. There is a blank line between output blocks.

Input

The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (1 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.

Output

Output the list of input strings, arranged from \`\`most sorted'' to \`\`least sorted''. If two or more strings are equally sorted, list them in the same order they are in the input file.

Sample Input

1
    
    10 6
    AACATGAAGG
    TTTTGGCCAA
    TTTGGCCAAA
    GATCAGATTT
    CCCGGGGGGA
    ATCGATGCAT

Sample Output

CCCGGGGGGA
    AACATGAAGG
    GATCAGATTT
    ATCGATGCAT
    TTTTGGCCAA
    TTTGGCCAAA
      
       
      
       
        
       题目大意：给你一系列DNA序列，根据他们的逆序数进行排序，按逆序数对由小到大输出，逆序数相等的时候，根据输入的前后顺序输出，
      
       
      
       
        
       稍微提一下逆序数，就是当i<j时，a[i]>a[j],比如说AGCT,G < C,G和C就是一对逆序数，其实就是求每个字母比他后面字母大的个数
      
       
      
       
        
       思路：要用结构体储存字符串和他本身的逆序数，这里面用到了
       
        stable_sort()，stable_sort()可保证相等元素的原本相对次序在排序后保持不变。
      
       
      
       
       
        而sort（）不能保证这一点。
      
       
      
       
       
        AC代码：
      
       
      
       
       
        
       
        #include <string>  
    #include <iostream>  
    #include <algorithm>  
    #include <cstdio>  
    using namespace std;  
    struct DNA{  
        string str;  
        int count;   //用来记录这个字符串中的逆序数对 
    }w[1005];  
    bool cmp(DNA x,DNA y){  
        return x.count < y.count;  
    }  	
    int main(){  
        int s, n, t;  
        cin >> t;  
        while(t--){  
            scanf("%d %d",&s,&n);  
            for(int i = 0; i < n; i++){  
                cin>>w[i].str;
                w[i].count = 0;  
                for(int j = 0; j < s; j++)              
                    for(int k = j + 1; k < s; k++)                   
                        if(w[i].str[j] > w[i].str[k]) 
    			w[i].count++;                             
            }  
            stable_sort(w, w + n, cmp);  
            for(int i = 0; i < n; i++) 
                cout<< w[i].str <<endl;    
        }  
        return 0;  
    }