TCS_CODEVITA_QUESTION(해결책 필요)

우체국 우체국 택배부가 엉망입니다. 밴에 실어야 할 소포들이 임의의 무게 순서로 일렬로 늘어서 있습니다. Head Post Master는 한 가지 예외를 제외하고 소포 무게가 증가하는 순서대로 소포를 정렬하기를 원합니다. 그는 가장 무거운 (아마도 가장 귀중한) 소포를 사무실 근처에 보관하기를 원합니다.

문제 설명
우체국 택배칸이 엉망입니다. 밴에 실어야 할 소포들이 임의의 무게 순서로 일렬로 늘어서 있습니다. Head Post Master는 한 가지 예외를 제외하고 소포 무게가 증가하는 순서대로 소포를 정렬하기를 원합니다. 그는 가장 무거운 (아마도 가장 귀중한) 소포를 사무실 근처에 보관하기를 원합니다.

당신과 당신의 친구는 이 상자들을 분류하려고 시도하고 당신은 한 번에 두 개의 상자를 교환하여 분류하기로 결정합니다. 그러한 교환에는 두 상자의 무게를 곱한 것과 같은 노력이 필요합니다.

목표는 최소한의 노력으로 필요에 따라 상자를 재배치하는 것입니다.

입력
첫 번째 줄은 상자 수(N)와 가장 무거운 상자가 있어야 하는 우체국장 사무실의 위치(k)를 지정하는 두 개의 공백으로 구분된 양의 정수로 구성됩니다.

두 번째 줄은 상자의 무게를 나타내는 N개의 공백으로 구분된 양의 정수로 구성됩니다. 두 개의 가중치가 동일하지 않다고 가정할 수도 있습니다.

출력
출력은 상자를 정렬된 순서로 가져오는 데 소요되는 총 노력을 제공하는 한 줄이며 위치 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!