最新消息:点击查看大S的省钱秘笈

POJ 1007 DNA Sorting C++版

POJ题解 Slyar 100浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

水题,又是关于逆序对的,玩了下STL的sort。

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.

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 (0 < 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''. Since two strings can be equally sorted, then output them according to the orginal order.

Sample Input

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Sample Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

Slyar:题意就是让你求逆序对,然后按照逆序对的大小将字符串输出,如果逆序对数目一样,则不要改变原来的顺序输出。

至于逆序对数...对于"ZWQM",因为Z>W>Q>M,则一共有6个逆序对:ZW、ZQ、ZM、WQ、WM、QM...就这样

暴力算出每个字符串的逆序对数目,然后排序就行了。玩了下sort,结果RE了好几次,最后发现又是因为数组开小了...=_=

转载请注明:Slyar Home » POJ 1007 DNA Sorting C++版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址