Test.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Test {

  public Test() {
		// TODO Auto-generated constructor stub
	}
	static class StrPair implements Comparable<StrPair>{
		
		public StrPair(String str, int idx) {
			super();
			this.str = str;
			this.idx = idx;
		}
		String str;
		int idx;
		@Override
		public int compareTo(StrPair o) {
			int ret= str.compareTo(o.str);
			if(ret==0){
				return o.idx-idx;
			}else{
				return ret;
			}
		}
	}
	/*
	 * 输入数据格式:
	 * N
	 * n1 n2 n3 n4
	 * 第一行是表示多少个不一样的数字，第二行为具体的数字，空格隔开
	 * 
	 */
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		String line=null;
		int N=0;
		line=scanner.nextLine();
		N=Integer.valueOf(line);
		List<String> numbers=new ArrayList<String>();
		for(int i=0;i<N;i++){
			line=scanner.next();
			numbers.add(line.trim());
		}
		//先排序，字典倒叙，首字母最大的在前面
		Collections.sort(numbers,Collections.reverseOrder());
		StringBuilder ret=new StringBuilder();
		while(!numbers.isEmpty()){
			int nn=numbers.size();
			char c=numbers.get(0).charAt(0);
			int end=nn;
			for(int i=1;i<nn;i++){
				//找到第一个首字母不是最大的位置，确定接下来要处理的范围
				if(numbers.get(i).charAt(0)!=c){
					end=i;
					break;
				}
			}
			if(end==1){
				//如果首字母最大的数字只有一个，那么就用它了
				ret.append(numbers.remove(0));
			}else{
				int i=0;
				//最大数字的字符数
				int maxLen=numbers.get(0).length();
				List<StrPair> pairs=new ArrayList<StrPair>();
				if(maxLen==1){
					throw new IllegalStateException("inpout data error ,has some duplicate entry");
				}
				//最大字符剩余串参与排序，因为首字母都是一样的，就比较剩余字符
				pairs.add(new StrPair(numbers.get(0).substring(1),0));
				for(i=1;i<end;i++){
					StringBuilder tmp=new StringBuilder(numbers.get(i).substring(1));
					int slen=tmp.length();
					//如果某个剩余数字的长度小于第一个，那么就给它添加上最大首字母，因为，挑了某个后，剩下来的数必然由这些首字母一样的数字构造出来。
				    if((slen+1)<maxLen){
				    	tmp.append(numbers.get(0).charAt(0));
				    }
				    //加入待排序集合
					pairs.add(new StrPair(tmp.toString(),i));
				}
				Collections.sort(pairs,Collections.reverseOrder());
				// 取第一个，最大的，对应的原始位置
				ret.append(numbers.remove(pairs.get(0).idx));
			}
		}
		System.out.println("result is :"+ret.toString());

	}

}