import java.util.Scanner;

public class Main
{	

	static int[] record = new int[4];
	static String[] output = null;
	static int[] idxes = null;
	static String[] tmpStrings = null;
	static int[] tmpInt = null;
	static int i1, j1;

	public static void main(String[] args)
	{

		Scanner cin = new Scanner(System.in);

		try
		{
			// Scanner cin = new Scanner(new File("C:\\input.txt"));
			int a = cin.nextInt();
			int b = cin.nextInt();
			output = new String[b];
			idxes = new int[b];
			tmpStrings = new String[b];
			tmpInt = new int[b];

			int idx = 0;
			String curLine = cin.nextLine();
			int curOrdernum;
			while (cin.hasNext())
			{
				curLine = cin.nextLine();

				initialize(curLine);

				curOrdernum = getOrderNum(curLine);

				output[idx] = curLine;
				idxes[idx] = curOrdernum;
				idx++;
			}

			mergeSort(0, output.length - 1);

			for (int i = 0; i < output.length; i++)
			{
				System.out.println(output[i]);
			}

		}
		catch (Exception e)
		{
			// TODO: handle exception
		}
	}

	static void mergeSort(int low, int hi)
	{
		if (low < hi)
		{
			int mid = low + (hi - low) / 2;
			mergeSort(low, mid);
			mergeSort(mid + 1, hi);
			merge(low, mid, hi);

		}
	}

	static void merge(int low, int mid, int hi)
	{
		for (int i = low; i <= hi; i++)
		{
			tmpStrings[i] = output[i];
			tmpInt[i] = idxes[i];
		}
		i1 = low;
		j1 = mid + 1;

		for (int k = low; k <= hi; k++)
		{
			if (i1 > mid)
			{
				output[k] = tmpStrings[j1];
				idxes[k] = tmpInt[j1++];
			}
			else if (j1 > hi)
			{
				output[k] = tmpStrings[i1];
				idxes[k] = tmpInt[i1++];
			}
			else if (tmpInt[i1] <= tmpInt[j1])
			{
				output[k] = tmpStrings[i1];
				idxes[k] = tmpInt[i1++];
			}
			else
			{
				output[k] = tmpStrings[j1];
				idxes[k] = tmpInt[j1++];
			}
		}

	}

	static void initialize(String curLine)
	{
		for (int i = 0; i < record.length; i++)
		{
			record[i] = 0;
		}

		for (int i = 0; i < curLine.length(); i++)
		{
			char curChar = curLine.charAt(i);
			record[getCharidx(curChar)]++;
		}
	}

	static int getCharidx(char c)
	{
		switch (c)
		{
			case 'A':
				return 0;
			case 'C':
				return 1;
			case 'G':
				return 2;
			case 'T':
				return 3;
			default:
				return -1;
		}

	}

	static int getOrderNum(String curLine)
	{
		int retval = 0;
		int idx = 0;

		for (int i = 0; i < curLine.length(); i++)
		{
			idx = getCharidx(curLine.charAt(i));
			record[idx]--;

			idx--;
			while (idx >= 0)
			{
				retval += record[idx--];
			}
		}
		return retval;

	}

}

• Re:一次AC， Java 代码 晒晒 (22) alvin2 2013-03-13 11:18:04
• Re:一次AC， Java 代码 晒晒 (2972) 20105391 2014-05-03 20:47:58