Posted on 2010-10-11 20:28
李东亮 阅读(1828)
评论(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;
}