Posted on 2010-10-11 20:28
李東亮 閱讀(1889)
評論(0) 編輯 收藏 引用
DNA Sorting(ZOJ
1188)
本題應該來說是一道比較容易的題，但是我覺得確實一道比較好的題：為了解決這道題可以寫很短的代碼，也可以寫很長的代碼；可以寫出比較高效的代碼，也可以寫出比較低效的代碼。
原題大家可以到ZOJ上查看，本處就不累述了。題目大意就是根據一個由ATCG字符組成的字符串的逆序數進行排序，然后輸出結果，如果有兩個字符串的逆序數相同則按照其輸入順序輸出，即要求排序函數是穩定的。至此，本題的思路已經很清晰了：接收數據à計算逆序à排序à輸出結果。
這里關鍵步驟是排序，要求穩定排序，因此C語言中的qsort和STL中的sort不再適用，而要自己編寫排序函數或者適用STL中的stable_sort。字符串逆序數的計算可以在輸入以后計算，也可以在輸入的同時就計算，根據接收字符串的方式而定，如果是整行接收的，只能以后再算了；如果是逐字符接收的，則可以邊接收邊計算。此處為了方便處理采用了整行接收的方法。具體代碼如下：
#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;
}