Codeforces #49 (div2) D "Physical Education"

問題：http://codeforces.com/contest/53/problem/D

プラクティス．

与えられた数値列を指定された数値列の順番にするために必要なスワップ回数とスワップ位置の組を求める．最小値である必要はない．

単純にソートの要領．

コード

import java.util.*;

public class D_PhysicalEducation {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int[] a = new int[n+1];
		for (int i = 1; i <= n; ++i) {
			a[i] = s.nextInt();
		}
		int[] b = new int[n+1];
		for (int i = 1; i <= n; ++i) {
			b[i] = s.nextInt();
		}
		List<int[]> list = new ArrayList<int[]>();
		for (int i = 1; i <= n; ++i) {
			int j = i + 1;
			for (; j <= n; ++j) {
				if (a[i] == b[j]) {
					break;
				}
			}
			for (; j <= n && j != i; --j) {
				list.add(new int[] { j - 1, j});
				swap(b, j - 1, j);
			}
		}
		System.out.println(list.size());
		for (int[] is : list) {
			System.out.println(is[0] + " " + is[1]);
		}
	}

	static void swap(int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
}