原题如下:
DNA Sorting
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 70970 Accepted: 28300
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
Source
East Central North America 1998
我的java程序如下:
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
int numOfChars = cin.nextInt();
int numOfStrings = cin.nextInt();
cin.nextLine();
String strings[] = new String[numOfStrings];
int degrees[] = new int[numOfStrings];//存储每个字符串的sortedness
for(int i = 0; i < numOfStrings; i++){//求得每个字符串的sortedness,并存储在数组degrees[]中
degrees[i] = 0;
strings[i] = cin.nextLine();
for(int j = 0; j < numOfChars; j++){
if(strings[i].charAt(j) == 'A'){//如果当前字符是A,后面不管是什么字符,sortedness都不变
}else if (strings[i].charAt(j) == 'C'){//如果当前字符是C,后面若有A,则sortedness+1
for(int k = j+1; k < numOfChars; k++){
if(strings[i].charAt(k) == 'A'){
degrees[i]++;
}
}
}else if (strings[i].charAt(j) == 'G'){//如果当前字符是G,后面若有A或C,则sortedness+1
for(int k = j+1; k < numOfChars; k++){
if(strings[i].charAt(k) == 'A'|| strings[i].charAt(k) == 'C'){
degrees[i]++;
}
}
}else{//若当前字符是T,后面有几个非T的字符,sortedness就加几
for(int k = j+1; k < numOfChars; k++){
if(strings[i].charAt(k) != 'T'){
degrees[i]++;
}
}
}
}
//System.out.println(degrees[i]);
}//outer for
int minIndex = 0;
for(int i = 0; i < numOfStrings; i++){
int min = Integer.MAX_VALUE;
for(int j = i; j < numOfStrings; j++){
if(degrees[j] < min){
min = degrees[j];
minIndex = j;
}
}
System.out.println(strings[minIndex]);
int tmp = degrees[i];
degrees[i] = degrees[minIndex];
degrees[minIndex] = tmp;
String tmpString = strings[i];
strings[i] = strings[minIndex];
strings[minIndex] = tmpString;
}
}//main
}
忘各位朋友多多指教!
分享到:
相关推荐
DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34868 Accepted: 13480 Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are ...
北大POJ1007-DNA Sorting 解题报告+AC代码
poj dna sorting 问题,研究的ac coderrrrrrr
poj1007 AC代码 0MS过题写法 不过是个水题 哈哈哈哈
poj1007题代码,DNA问题,C++语言,map
北大POJ1094-Sorting It All Out 解题报告+AC代码
ACM是很好的,多在OJ上练习,你会有惊喜的。很能增加您的技能。
POJ1048,加强版的约瑟夫问题 难度中等
NULL 博文链接:https://128kj.iteye.com/blog/1705139
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem....
POJ 1328 java做!雷达问题!java版本!AC答案~
用java的biginteger实现的poj1001,比较简单的方法
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
北大POJ2002-Squares 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1744222
北大poj JAVA源码
提示:二叉树遍历而已,给出前序和中序,求后序 解题思路 1、前序遍历的第一个字母必是 根 2、在中序遍历的字母串中找出 根字母,那么根字母左右两边的字符串就分别是它的左、右子树 3、利用递归复原二叉树(把...
这是East Central North America 1998的测试数据,包括POJ的1007DNA Sorting等问提,利于大家思考。
poj 2785 4 Values whose Sum is 0 测试数据 解题报告: http://blog.csdn.net/qq7366020/article/details/8623208
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类