はまやんはまやんはまやん

hamayanhamayan's blog

Little Robber Girl's Zoo (Codeforces 359 : Div2 B)

問題

http://codeforces.com/contest/686/problem/B

n個の整数列 a1, a2, ..., an がある。
l番目からr番目(r - l + 1が偶数)について、lとl+1番目、l+2とl+3番目、...、r-1とr番目を入れ替える処理をする。
与えられた整数列が非減少列となるようには、どのような範囲で処理を行っていけばいいか。

1 <= n <= 100
1 <= ai <= 10^9
処理の回数は20000回を超えない

思考の流れ
  1. ソートアルゴリズムはそう多くない
  2. まだDiv2 Bということはそんなに難しいことは聞いてこない
  3. ソートで簡単かつよく出てくるといえば「バブルソート
  4. 今回は入れ替え処理をする幅を2にしてしまえば、隣り合う要素のスワップとなる
  5. 100要素に対して20000回なら、バブルソートで余裕
解法

http://codeforces.com/contest/686/submission/18771367

冗長な気もしますが…

#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define INF INT_MAX/2
int n;
int a[100];

//-----------------------------------------------------------------

cin >> n;
rep(i, 0, n) cin >> a[i];

rep(i, 0, n - 1)
{
	int _min = INF, _min_i;
	rep(j, i, n)
	{
		if (a[j] < _min)
		{
			_min = a[j];
			_min_i = j;
		}
	}

	rrep(j, _min_i - 1, i)
	{
		printf("%d %d\n", j+1, j + 2);
		swap(a[j], a[j + 1]);
	}
}