Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-21SRM300台を練習していく part3

SRM 307 PartSorting

|  SRM 307 PartSorting - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 307 PartSorting - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6447

swap可能な範囲で大きな数を前に持ってこようと試みる。


public class PartSorting {

	public int[] process(int[] data, int nSwaps) {
		int len = data.length;
		for (int x = 0 ; x < len ; x++) {
			int max = data[x];
			int maxidx = x;
			for (int i = x + 1 ; i < len ; i++) {
				if (max < data[i] && i - x <= nSwaps) {
					max = data[i];
					maxidx = i;
				}
			}
			nSwaps -= maxidx - x;
			for (int j = maxidx ; j >= x + 1 ; j--) {
				int tmp = data[j];
				data[j] = data[j-1];
				data[j-1] = tmp;
			}
		}
		return data;
	}
}