UVa OJ - 612 DNA Sorting

The following program is my ACcepted code for UVA-612 .
It's a for everybody to learn and discuss.
If there is any mistake or comment, please let me know.  :D

此乃UVA 612 的AC code!

歡迎一同討論學習，如有錯誤與任何建議請留言 : )

點這裡看題目 Click here to see this Problem!

一個非常好的練習題
題目敘述很簡單，本題精華在於使用struct 和 sort
使用 struct 可以將 DNA 跟計算後的 measure 包在一起
如此在排序 measure 之後，只要直接輸出即可
PS: 請注意如果measure相同，要照著input的順序輸出! 所以我使用 stable_sort

A good practice problem!
The description is simple, but you have to be careful.
The essence of this problem is using struct and sort.
Using struct can block the DNA data and measure.
Then after we sort the measures, we only have to output the DNA!
PS: Please not that: if measures are the same, output the same order they are in the input file!

//This program is for UVA 612 DNA Sorting
//題目來源 Problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=553
#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<algorithm>//stable_sort
using namespace std;

typedef struct
{
    char dna[60];
    int measure;
}strDna;

strDna DNA[110];//save DAN and measure

void initial()
{
    for(int i=0; i<110; i++)
    {
        memset(DNA[i].dna, '\0', sizeof(DNA[i].dna) );
        DNA[i].measure = 0;
    }
}


//claculate the measure of unsortedness in DNA[index]
int calMeasure(int index, int len)
{
    int mea = 0;
    for(int i = 0; i < len - 1; i++)
        for(int j = i + 1; j < len; j++)
            if(DNA[index].dna[i] > DNA[index].dna[j])
                mea ++;
    return mea;
}

//this is the compare function for sort
bool cmp(strDna a, strDna b)
{
    return a.measure < b.measure;
}

int main()
{
    int n, m, t;
 
    while(scanf("%d", &t) != EOF)
    {
        for(int c = 0; c < t; c++)
        {
            if(c != 0)//if it's not the first case, we should have one blank line between test cases.
                printf("\n");
             
            scanf("%d %d\n", &n, &m);
         
            initial();
         
            for(int i = 0; i < m; i++)
            {
                scanf("%s", &DNA[i].dna);
                DNA[i].measure = calMeasure(i, n);
                //printf("%d\n", DNA[i].measure);
            }
         
            stable_sort(DNA, DNA + m, cmp);
         
            for(int i = 0; i < m; i++)
                printf("%s\n", DNA[i].dna);
        }
    }
 
    return 0;
}

Please feel free to use it after adding this blog as an reference. (http://autekroy.blogspot.tw) If there is any mistake or comment, please let me know. :D 

歡迎使用與分享任何內容，但請記得標示此部落格為出處。(http://autekroy.blogspot.tw/) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )