DOJ Beginner Contest 8 E - Swap Two Elements
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 8
- 問題
- E - Swap Two Elements
長さ の順列 が与えられます。次の操作を何回でも行えます。
- を選ぶ。 のうち最小の要素と 2 番目に小さい要素の位置を入れ替える。
を昇順にするための操作回数の最小値と、その回数を達成する操作の列を 1 つ出力する問題です。 の総和は 以下です。
答えは の転倒数(位置が前なのに値が大きい組 の個数)です。
1 回の操作で転倒数は 1 しか変わらない
Section titled “1 回の操作で転倒数は 1 しか変わらない”区間 で入れ替える 2 つの値を 、その位置を とします。
- 区間内の と の間にある要素は、どれも と より大きいです( が区間で最も小さい 2 つだからです)。 と の間にある要素から見ると、 と はどちらも自分より小さいままです。そのため、この要素が関わる転倒の数は、入れ替えても変わりません。
- より前、 より後ろの要素から見ても、 と の両方が同じ側にあることは変わらないので、転倒の数は変わりません。
変わるのは と の組だけで、転倒数はちょうど 増えるか 減ります。昇順の順列の転倒数は なので、操作は転倒数の回数以上必要です。
隣どうしの入れ替えで達成できる
Section titled “隣どうしの入れ替えで達成できる”とすると、区間は の 2 つだけなので、この操作は隣どうしの入れ替えです。バブルソートのように、 となっている隣の組を入れ替えるたびに、転倒数は ずつ減ります。したがって、ちょうど転倒数の回数で昇順にできます。
の総和が 以下なので、 のバブルソートで十分間に合います。
Python
for _ in range(int(input())): N = int(input()) A = list(map(int, input().split())) ans = [] for _ in range(N): for i in range(1, N): if A[i - 1] > A[i]: ans.append((i - 1, i)) A[i - 1], A[i] = A[i], A[i - 1] print(len(ans)) for x, y in ans: print(x + 1, y + 1)バブルソートを行い、入れ替えた隣の組 を記録して出力しています。