少なくとも 1 個、最大で 2*k - 1 個の反転が除去されることを証明してください
「反転が削除される」とはどういう意味かわかりません。また、どこから始めればよいかわかりません。
1 に答える
3
リストが1, 3, 2, 4に変更されている1, 2, 3, 4場合、反転は削除されています。
a[i]とa[i+k]が順不同だったため、少なくとも 1 つの反転を削除したことは明らかです。それよりも大きい場合は反転を修正する2*k - 1ため、せいぜい削除します。その下のすべてよりも小さい場合も同じです。したがって、あなたが持つことができる最大のものは(最後の 1 はすでに数えたものです) に等しいです。a[i]a[i+1], ... ,a[i+k-1]k-1a[i+k]k-1 + k-1 + 12k - 1
例: 1,10,3,4,5,6,7,8,9,2-> switch a[2]with a[10], k = 8, 2 は 10 よりも小さくなり、2 も 3-9 (7 つの数字) よりも小さくなります。さらに 10 は 3-9 よりも大きく、これもまた 7 の数字です。7 + 7 + 1 = 15 = 2*8 - 1
于 2012-11-04T03:16:30.823 に答える