Posted on 2010-10-11 20:28
李東亮 閱讀(1889)
評論(0) 編輯 收藏 引用
DNA Sorting(ZOJ
1188)
本題應(yīng)該來說是一道比較容易的題，但是我覺得確實(shí)一道比較好的題：為了解決這道題可以寫很短的代碼，也可以寫很長的代碼；可以寫出比較高效的代碼，也可以寫出比較低效的代碼。
原題大家可以到ZOJ上查看，本處就不累述了。題目大意就是根據(jù)一個(gè)由ATCG字符組成的字符串的逆序數(shù)進(jìn)行排序，然后輸出結(jié)果，如果有兩個(gè)字符串的逆序數(shù)相同則按照其輸入順序輸出，即要求排序函數(shù)是穩(wěn)定的。至此，本題的思路已經(jīng)很清晰了：接收數(shù)據(jù)à計(jì)算逆序à排序à輸出結(jié)果。
這里關(guān)鍵步驟是排序，要求穩(wěn)定排序，因此C語言中的qsort和STL中的sort不再適用，而要自己編寫排序函數(shù)或者適用STL中的stable_sort。字符串逆序數(shù)的計(jì)算可以在輸入以后計(jì)算，也可以在輸入的同時(shí)就計(jì)算，根據(jù)接收字符串的方式而定，如果是整行接收的，只能以后再算了；如果是逐字符接收的，則可以邊接收邊計(jì)算。此處為了方便處理采用了整行接收的方法。具體代碼如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int degree;
char str[50];
bool operator < (const node& n) const
{
return degree <= n.degree;
}
};
node mat[100];
int main(void)
{
int t;
int m, n;
int i, j, k;
int deg;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &m, &n);
for (i = 0; i < n; ++i)
{
scanf("%s", mat[i].str);
deg = 0;
for (j = 0; j < m-1; ++j)
{
for (k = j; k < m; ++k)
{
if (mat[i].str[j] > mat[i].str[k])
++deg;
}
}
mat[i].degree = deg;
}
stable_sort(mat, mat+n);
for (i = 0; i < n; ++i)
{
printf("%s\n", mat[i].str);
}
if (t != 0)
printf("\n");
}
return 0;
}