TCS_CODEVITA_QUESTION(penyelesaian diperlukan)

Bahagian bungkusan Ibu Pejabat Pos berada dalam keadaan kucar-kacir. Bungkusan-bungkusan yang perlu dimuatkan ke dalam van telah dibariskan dalam satu barisan dalam susunan berat yang sewenang-wenangnya. Ketua Jawatan Guru mahu mereka diisih mengikut susunan berat petak yang semakin meningkat, dengan satu pengecualian. Dia mahu bungkusan yang paling berat (dan mungkin yang paling berharga) disimpan berdekatan dengan pejabatnya.

Penerangan Masalah
Bahagian bungkusan Ibu Pejabat Pos berada dalam keadaan kucar-kacir. Bungkusan-bungkusan yang perlu dimuatkan ke dalam van telah dibariskan dalam satu barisan dalam susunan berat yang sewenang-wenangnya. Ketua Jawatan Guru mahu mereka diisih mengikut susunan berat petak yang semakin meningkat, dengan satu pengecualian. Dia mahu bungkusan yang paling berat (dan mungkin yang paling berharga) disimpan berdekatan dengan pejabatnya.

Anda dan rakan anda cuba mengisih kotak ini dan anda memutuskan untuk mengisihnya dengan menukar dua kotak pada satu masa. Pertukaran sebegini memerlukan usaha yang sama dengan hasil darab kedua-dua kotak itu.

Objektifnya adalah untuk meletakkan semula kotak seperti yang diperlukan dengan usaha yang minimum.

Input
Baris pertama terdiri daripada dua integer positif yang diasingkan ruang memberikan bilangan kotak (N) dan kedudukan pejabat Ketua Pos Guru (k) di mana kotak paling berat mesti berada.

Barisan kedua terdiri daripada N integer positif dipisahkan ruang yang memberikan pemberat kotak. Anda mungkin menganggap bahawa tiada dua pemberat yang sama.

Output
Keluaran ialah satu baris yang memberikan jumlah usaha yang diambil untuk mendapatkan kotak dalam susunan yang disusun dan yang paling berat dalam kedudukan k.

Kekangan
N<=50

Berat <= 1000

Tahap Kesukaran
Kompleks

Had Masa (saat)
1

Contoh
Contoh 1

Input

5 2

20 50 30 80 70

Output

3600

Penjelasan

Terdapat 5 kotak (N=5) dan kotak yang paling berat mestilah berada di kedudukan 2 (k=2). Jika kita melihat pada susunan akhir (diisih, dengan yang paling berat pada kedudukan 2), ia sepatutnya 20 80 30 50 70. Jika kita melihat ini, kita perhatikan bahawa hanya 50 dan 80 petak yang perlu ditukar. Oleh kerana ini memerlukan usaha hasil darab, usaha ialah 4000.

Pengurangan lanjut boleh diperolehi jika kita menggunakan pakej terkecil (20) sebagai perantara. Jika kita menukar 20 dengan 50 (usaha 1000), kemudian dengan 80 (usaha 1600) dan kembali dengan 50 lagi (usaha 1000), kesannya adalah sama, dengan jumlah usaha 3600 (kurang daripada usaha yang diperolehi secara langsung. gerakkan) usaha

Hasil selepas urutan pertukaran yang optimum ialah

50 20 30 80 70

50 80 30 20 70

20 80 30 80 70

Memandangkan ini memerlukan usaha sebanyak 3600, output ialah 3600.

Contoh 2

Input

6 3

30 20 40 80 70 60

Output

7600

Penjelasan

Terdapat 6 petak, dan yang paling berat sepatutnya berada di kedudukan 3. Oleh itu pesanan terakhir perlu 20 30 80 40 60 70. Jika kita melihat pada kedudukan awal, kita melihat bahawa 20 dan 30 perlu ditukar ( usaha 600), 40 dan 80 perlu ditukar (usaha 3200) dan 60 dan 70 perlu ditukar (usaha 4200). Oleh itu jumlah usaha ialah 600 3200 4200=8000.

Jika kita menggunakan pendekatan yang sama seperti dalam Contoh 1, kita mendapat usaha berikut

(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

Jumlah usaha sebanyak 7600 diperolehi dan bukannya usaha sebanyak 8000, yang merupakan output.

Atas ialah kandungan terperinci TCS_CODEVITA_QUESTION(penyelesaian diperlukan). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!