DNA Sorting
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 33807 | Accepted: 13022 |
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.
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
实现Java的Comparator接口即可
import java.util.*; class DNA { private String str = null; private int sortNum = 0; public DNA(String input) { str = input; int num = 0; for(int i = 0; i < str.length()-1; i++) { for(int j = i+1; j < str.length(); j++) if(str.charAt(i) > str.charAt(j)) num++; } sortNum = num; } public int getSortNum() { return sortNum; } public String toString() { return str; } } class DNAComparator implements Comparator { public int compare(Object o1, Object o2) { DNA d1 = (DNA)o1; DNA d2 = (DNA)o2; if(d1.getSortNum() > d2.getSortNum()) return 1; else if(d1.getSortNum() == d2.getSortNum()) return 0; else return -1; } } public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); String[] str = cin.nextLine().split(" "); int col = Integer.valueOf(str[0]).intValue(); int row = Integer.valueOf(str[1]).intValue(); List list = new ArrayList(); for(int i = 0; i < row; i++) { DNA dna = new DNA(cin.nextLine()); list.add(dna); } Collections.sort(list, new DNAComparator()); print(list); } private static void print(List list) { Iterator iter = list.iterator(); while(iter.hasNext()) { System.out.println(iter.next()); } } }
发表评论
-
POJ ACM习题【No.2328】
2009-07-05 19:43 895Guessing Game Time ... -
POJ ACM习题【No.3157】
2009-04-26 23:54 1633Java vs C++ Time Lim ... -
POJ ACM习题【No.2924】
2009-04-26 11:52 919Gauß in Elementary School ... -
POJ ACM习题【No.3176】
2009-04-26 10:53 1043Cow Bowling Time Lim ... -
POJ ACM习题【No.3173】
2009-04-25 23:30 900Parkside's Triangle ... -
POJ ACM习题【No.2845】
2009-04-25 22:25 120801000001 Time Limit: ... -
POJ ACM习题【No.2140】
2009-04-25 21:26 932Herd Sums Time Limit ... -
POJ ACM习题【No.1969】
2009-04-25 20:59 858Count on Canton Time ... -
POJ ACM习题【No.2840】
2009-04-25 19:24 1002Big Clock Time Limit ... -
POJ ACM习题【No.2521】
2009-04-24 22:41 846How much did the businessman l ... -
POJ ACM习题【No.1326】
2009-04-24 22:14 1008Mileage Bank Time Li ... -
POJ ACM习题【No.3325】
2009-04-24 21:15 1087ICPC Score Totalizer Software ... -
POJ ACM习题【No.2756】
2009-04-24 20:28 770Autumn is a Genius T ... -
POJ ACM习题【No.3062】
2009-04-24 20:10 804Celebrity jeopardy ... -
POJ ACM习题【No.1547】
2009-04-23 20:03 770Clay Bully Time Limi ... -
POJ ACM习题【No.1552】
2009-04-23 19:39 747Doubles Time Limit: ... -
POJ ACM习题【No.1565】
2009-04-22 22:40 839Skew Binary Time Lim ... -
POJ ACM习题【No.2403】
2009-04-22 22:18 857Hay Points Time Limi ... -
POJ ACM习题【No.1862】
2009-04-22 20:12 694Stripies Time Limit: ... -
POJ ACM习题【No.3224】
2009-04-22 19:57 740Lab杯 Time Limit: 1 ...
相关推荐
方便大家有针对性地联系 祝大家AC愉快~
pojACM题目分类,便于各类型同学分别做题有所参考
相信大家在做poj上的题目的时候如果没有分类的话很迷茫吧....这里有一份目前比较全面的poj题目分类..
02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ...
acm数据结构总结.doc acm数据结构总结.doc
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
本文件是ACM里的一些题目的源码、原题和习题的分析及详细解答。欢迎各位下载
http://acm.pku.edu.cn/JudgeOnline/ acm的AC解题报告
POJ ACM 1015 Jury Compromise 两种解法 解题报告
西工大C语言POJ习题答案.docx
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
poj 2007 Scrambled Polygon.md
poj 3183 Stump Removal.md
poj 2430 Lazy Cows.md
poj 2900 Griddy Hobby.md
poj 3435 Sudoku Checker.md
poj 1984 Navigation Nightmare.md
poj 2174 Decoding Task.md
poj 2386 Lake Counting.md
poj 3585 Accumulation Degree.md