Codeforces ラウンド #277.5 (ディビジョン 2)-A. SwapSort（ソート）_html/css_WEB-ITnose

SwapSort

テストごとの制限時間

テストごとのメモリ制限

入力

出力

この問題での目標n 個の整数で構成される配列を最大 n 個のスワップでソートすることです。指定された配列について、配列を非降順でソートするスワップのシーケンスを見つけます。スワップは、次々と連続して実行されます。

この問題では、スワップの数を最小限に抑える必要がないことに注意してください。あなたのタスクは、n 以下のシーケンスを見つけることです。

入力

入力の最初の行には、整数 n (1?≤?n?≤?3000) が含まれています。配列要素の数。 2 行目には配列の要素が含まれます:a0,?a1,?...,?an?-?1 (?-?109?≤?ai?≤?109)。ai は配列の i 番目の要素です。 。要素は、左から右に 0 から n?-?1 まで番号付けされます。一部の整数は配列内に複数回出現する場合があります。

出力

最初の行で print k (0?≤?k?≤?n) ?スワップの数。次の k 行には、k スワップの説明を 1 行に 1 つずつ含める必要があります。各スワップは、要素 ai と aj のスワップを表す整数 i, j (0?≤?i,?j?≤?n?-?1) のペアとして出力する必要があります。ペアのインデックスは任意の順序で出力できます。スワップは、出力に表示される順序で、最初から最後まで実行されます。 i?=?j を出力し、同じ要素のペアを複数回交換することができます。

複数の答えがある場合は、それらのいずれかを出力します。少なくとも 1 つの答えが存在することが保証されています。

サンプル テスト

入力

55 2 5 1 4

出力

20 34 2

入力

610 20 20 40 60 60

出力

入力

出力

2101 100

题意：给一组数、问怎么可以

最小回目の交換を実行し、昇順順序を実行して交換プロセスを出力します。

解题思路：当時比赛然脑残了、WA了二つ発行、特徴似及逆序数很像、各元素について都找他後面の最大値、若最大値と当前の位置の値が等しくない、すなわち交替、保存次交替记录、最終出即可。