PKU 1007文字列逆シーケンス

2162 ワード

0/1の危害ですね、joel on softwareで言及したことがありますが、やはり、めちゃくちゃに書いてあります.

public class Measure {

	private char[] sequence;
	private int measure;

	public Measure() {
		this("");
	}

	public Measure(String seqString) {
		this.sequence = seqString.toCharArray();
		this.measure = 0;
	}

	public int calculate() {
		this.mergeSort(0, this.sequence.length - 1);
		return this.measure;
	}

	private void mergeSort(int begin, int end) {
		int middle = (begin + end) / 2;
		if (begin < end) {
			this.mergeSort(begin, middle);
			this.mergeSort(middle + 1, end);
			this.merge(begin, middle, end);
		}
	}

	private void merge(int begin, int middle, int end) {
		int from = begin;
		int to = end;
		int temoMiddle = middle;
		char[] tempSeq = new char[end + 1];
		int position = 0;
		while (begin <= temoMiddle && middle + 1 <= end){
			if (this.sequence[begin] < this.sequence[middle + 1]) {
				tempSeq[position] = this.sequence[begin++];
			} else {
				this.measure += (temoMiddle + 1) - begin;
				tempSeq[position] = this.sequence[middle + 1];
				middle++;
			}
			position++;
		}
		
		while (begin <= temoMiddle) {
			tempSeq[position++] = this.sequence[begin++];
		}
		
		while (middle < end) {
			tempSeq[position++] = this.sequence[middle + 1];
			middle++;
		}
		System.arraycopy(tempSeq, 0, this.sequence, from, to - from + 1);
		System.out.println("measure:" + measure);
		System.out.println("seq " + new String(this.sequence));
	}

	public int getMeasure() {
		return measure;
	}

	public void setMeasure(int measure) {
		this.measure = measure;
	}

	public String getSequence() {
		return new String(sequence);
	}

	public void setSequence(String sequence) {
		this.sequence = sequence.toCharArray();
	}
}