TCS_CODEVITA_QUESTION(解決策が必要)

本店郵便局の小包課は混乱しています。 バンに積み込む必要のある荷物は、任意の重量順に一列に並べられています。 郵便局長は、1 つの例外を除いて、小包の重量の昇順に並べ替えることを望んでいます。 彼は最も重い (そしておそらく最も価値のある) 小包をオフィスの近くに置いておきたいと考えています。

問題の説明
本店郵便局の小包課は混乱している。 バンに積み込む必要のある荷物は、任意の重量順に一列に並べられています。 郵便局長は、1 つの例外を除いて、小包の重量の昇順に並べ替えることを望んでいます。 彼は最も重い (そしておそらく最も価値のある) 小包をオフィスの近くに置いておきたいと考えています。

あなたとあなたの友人はこれらの箱を並べ替えようとして、一度に 2 つの箱を交換して並べ替えることにしました。 このような交換には、2 つのボックスの重量の積に等しい労力が必要です。

目的は、最小限の労力で必要に応じてボックスの位置を変更することです。

入力
最初の行は、スペースで区切られた 2 つの正の整数で構成され、箱の数 (N) と、最も重い箱があるはずの郵便局長のオフィスの位置 (k) を示します。

2 行目は、ボックスの重みを示す N 個のスペースで区切られた正の整数で構成されます。 等しい重みは 2 つとしてないと考えられるかもしれません。

出力
出力は 1 行で、ボックスをソート順に取得するのに要した総労力と、位置 k で最も重いボックスを取得するのに要した総労力を示します。

制約
N

ウェイト

難易度
複雑

制限時間 (秒)
1

例
例 1

入力

5 2

20 50 30 80 70

出力

3600

説明

5 つのボックス (N=5) があり、最も重いボックスは位置 2 (k=2) になければなりません。 最終的な順序 (並べ替え、位置 2 が最も重いもの) を見ると、20 80 30 50 70 となるはずです。これを見ると、50 と 80 の小包のみを交換する必要があることがわかります。 これには重みの積の労力がかかるので、労力は 4000 です。

最小のパッケージ (20) を中間として使用すると、さらに削減できます。 20 を 50 (努力値 1000) に交換し、次に 80 (努力値 1600) に交換し、再び 50 (努力値 1000) に交換した場合、効果は同じで、合計の努力値は 3600 になります (直接の努力で得られる労力よりも少なくなります)。動く）努力

最適な交換シーケンスの後の結果は次のとおりです

50 20 30 80 70

50 80 30 20 70

20 80 30 80 70

これには 3600 の労力がかかるため、出力は 3600 になります。

例 2

入力

6 3

30 20 40 80 70 60

出力

7600

説明

6 つの区画があり、最も重いものは位置 3 にあるはずです。したがって、最終的な順序は 20 30 80 40 60 70 になる必要があります。最初の位置を見ると、20 と 30 を交換する必要があることがわかります (努力値 600)、40 と 80 は交換する必要があります (努力値 3200)、60 と 70 は交換する必要があります (努力値 4200)。 したがって、合計の労力は 600 3200 4200=8000 となります。

例 1 と同じアプローチを使用すると、次のような取り組みが得られます

(600) 20 30 40 80 70 60

(3200) 20 30 80 40 70 60

(1200) 60 30 80 40 70 20

(1400) 60 30 80 40 20 70

(1200) 20 30 80 40 60 70

努力値 8000 ではなく、合計 7600 の努力値が得られ、それが成果となります。

以上がTCS_CODEVITA_QUESTION(解決策が必要)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。