`
kellychan
  • 浏览: 2796 次
  • 性别: Icon_minigender_2
  • 来自: 北京
最近访客 更多访客>>
社区版块
存档分类
最新评论

poj 1007 DNA Sorting java版

    博客分类:
  • poj
阅读更多
原题如下:
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

}


忘各位朋友多多指教!
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics