TCS_CODEVITA_QUESTION (Lösung erforderlich)

In der Paketabteilung des Hauptpostamtes herrscht Chaos. Die Pakete, die in die Transporter geladen werden müssen, sind in willkürlicher Gewichtsreihenfolge aufgereiht. Der Oberpostmeister möchte, dass die Pakete bis auf eine Ausnahme in aufsteigender Reihenfolge nach Gewicht sortiert werden. Er möchte, dass das schwerste (und vermutlich wertvollste) Paket in der Nähe seines Büros aufbewahrt wird.

Problembeschreibung
In der Paketabteilung der Hauptpost herrscht Chaos. Die Pakete, die in die Transporter geladen werden müssen, sind in willkürlicher Gewichtsreihenfolge aufgereiht. Der Oberpostmeister möchte, dass die Pakete bis auf eine Ausnahme in aufsteigender Reihenfolge nach Gewicht sortiert werden. Er möchte, dass das schwerste (und vermutlich wertvollste) Paket in der Nähe seines Büros aufbewahrt wird.

Sie und Ihr Freund versuchen, diese Kisten zu sortieren, und Sie beschließen, sie zu sortieren, indem Sie jeweils zwei Kisten austauschen. Ein solcher Austausch erfordert einen Aufwand, der dem Produkt der Gewichte der beiden Kisten entspricht.

Ziel ist es, die Kartons mit minimalem Aufwand nach Bedarf neu zu positionieren.

Eingabe
Die erste Zeile besteht aus zwei durch Leerzeichen getrennten positiven ganzen Zahlen, die die Anzahl der Kartons (N) und die Position des Büros des Hauptpostmeisters (k) angeben, wo sich der schwerste Karton befinden muss.

Die zweite Zeile besteht aus N durch Leerzeichen getrennten positiven ganzen Zahlen, die die Gewichte der Boxen angeben. Sie können davon ausgehen, dass keine zwei Gewichte gleich sind.

Ausgabe
Die Ausgabe ist eine Zeile, die den Gesamtaufwand angibt, der aufgewendet wurde, um die Kisten in sortierter Reihenfolge zu bringen, und die schwersten an Position k.

Einschränkungen
N<=50

Gewichte <= 1000

Schwierigkeitsgrad
Komplex

Zeitlimit (Sekunden)
1

Beispiele
Beispiel 1

Eingabe

5 2

20 50 30 80 70

Ausgabe

3600

Erklärung

Es gibt 5 Kisten (N=5) und die schwerste Kiste muss sich auf Position 2 (k=2) befinden. Wenn wir uns die endgültige Reihenfolge ansehen (sortiert, mit dem schwersten auf Position 2), sollte es 20 80 30 50 70 sein. Wenn wir uns das ansehen, stellen wir fest, dass nur die 50er und die 80er-Pakete ausgetauscht werden müssen. Da dies den Aufwand des Produkts der Gewichte erfordert, beträgt der Aufwand 4000.

Eine weitere Reduzierung kann erreicht werden, wenn wir das kleinste Paket (20) als Vermittler nutzen. Wenn wir 20 mit 50 (Aufwand 1000), dann mit 80 (Aufwand 1600) und wieder zurück mit 50 (Aufwand 1000) austauschen, ist der Effekt derselbe, mit einem Gesamtaufwand von 3600 (weniger als der Aufwand, der durch die direkte erzielt wird). bewegen)und die Anstrengung

Die Ergebnisse nach der optimalen Reihenfolge der Austausche sind

50 20 30 80 70

50 80 30 20 70

20 80 30 80 70

Da dies einen Aufwand von 3600 erfordert, beträgt die Ausgabe 3600.

Beispiel 2

Eingabe

6 3

30 20 40 80 70 60

Ausgabe

7600

Erklärung

Es gibt 6 Pakete und das schwerste sollte sich an Position 3 befinden. Daher muss die endgültige Reihenfolge 20 30 80 40 60 70 lauten. Wenn wir uns die Ausgangsposition ansehen, sehen wir, dass 20 und 30 vertauscht werden müssen ( Aufwand 600), 40 und 80 müssen getauscht werden (Aufwand 3200) und 60 und 70 müssen getauscht werden (Aufwand 4200). Somit beträgt der Gesamtaufwand 600 3200 4200=8000.

Wenn wir den gleichen Ansatz wie in Beispiel 1 verwenden, erhalten wir die folgenden Anstrengungen

(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

Es ergibt sich ein Gesamtaufwand von 7600 statt eines Aufwands von 8000, was der Ausgabe entspricht.

Das obige ist der detaillierte Inhalt vonTCS_CODEVITA_QUESTION (Lösung erforderlich). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!