TCS_CODEVITA_QUESTION(solution nécessaire)

La section colis du siège social de la Poste est en désordre. Les colis qui doivent être chargés dans les camionnettes ont été alignés dans un ordre de poids arbitraire. Le Chef de Poste souhaite qu'ils soient triés dans l'ordre croissant des poids des colis, à une exception près. Il veut que le colis le plus lourd (et probablement le plus précieux) soit conservé le plus près de son bureau.

Description du problème
Le service colis du siège social de la Poste est en désordre. Les colis qui doivent être chargés dans les camionnettes ont été alignés dans un ordre de poids arbitraire. Le Chef de Poste souhaite qu'ils soient triés dans l'ordre croissant des poids des colis, à une exception près. Il veut que le colis le plus lourd (et probablement le plus précieux) soit conservé le plus près de son bureau.

Vous et votre ami essayez de trier ces cartons et vous décidez de les trier en interchangeant deux cartons à la fois. Un tel échange nécessite un effort égal au produit des poids des deux caisses.

L'objectif est de repositionner les cartons selon les besoins avec un minimum d'effort.

Entrée
La première ligne est constituée de deux entiers positifs séparés par des espaces donnant le nombre de cartons (N) et la position du bureau du Chef de Poste (k) où doit se trouver le carton le plus lourd.

La deuxième ligne est constituée de N entiers positifs séparés par des espaces donnant les poids des cases. Vous pouvez supposer qu’il n’y a pas deux poids égaux.

Sortie
Le résultat est une ligne donnant l'effort total nécessaire pour trier les cartons, et le plus lourd en position k.

Contraintes
N<=50

Poids <= 1000

Niveau de difficulté
Complexe

Délai (secondes)
1

Exemples
Exemple 1

Entrée

5 2

20 50 30 80 70

Sortie

3600

Explication

Il y a 5 cartons (N=5) et le carton le plus lourd doit être en position 2 (k=2). Si l'on regarde la commande finale (triée, avec le plus lourd en position 2), elle devrait être de 20 80 30 50 70. Si l'on regarde cela, on remarque que seuls les 50 et les 80 colis doivent être échangés. Comme cela demande un effort du produit des poids, l'effort est de 4000.

Une réduction supplémentaire peut être obtenue si l'on utilise le plus petit colis (20) comme intermédiaire. Si l'on échange 20 contre 50 (effort 1000), puis avec 80 (effort 1600) et inversement avec 50 (effort 1000), l'effet est le même, avec un effort total de 3600 (inférieur à l'effort obtenu par le direct). bouger)et l'effort

Les résultats après la séquence optimale des échanges sont

50 20 30 80 70

50 80 30 20 70

20 80 30 80 70

Comme cela demande un effort de 3600, le résultat est de 3600.

Exemple 2

Entrée

6 3

30 20 40 80 70 60

Sortie

7600

Explication

Il y a 6 colis, et le plus lourd doit être en position 3. La commande finale doit donc être de 20 30 80 40 60 70. Si on regarde la position initiale, on voit qu'il faut échanger 20 et 30 ( effort 600), 40 et 80 doivent être échangés (effort 3200) et 60 et 70 doivent être échangés (effort 4200). L'effort total est donc de 600 3 200 4 200 = 8 000.

Si on utilise la même approche que dans l'exemple 1, on obtient les efforts suivants

(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

On obtient un effort total de 7600 plutôt qu'un effort de 8000, qui est le résultat.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!