TCS_CODEVITA_QUESTION（需要解决方案）

邮政总局的包裹区一片狼藉。 需要装载到货车上的包裹已按任意重量顺序排成一排。 邮政总站管理员希望按照包裹重量的升序对它们进行分类，但有一个例外。 他希望将最重（也可能是最有价值）的包裹放在离他办公室最近的地方。

问题描述
邮政总局的包裹区一片狼藉。 需要装载到货车上的包裹已按任意重量顺序排成一排。 邮政总站管理员希望按照包裹重量的升序对它们进行分类，但有一个例外。 他希望将最重（也可能是最有价值）的包裹放在离他办公室最近的地方。

您和您的朋友尝试对这些盒子进行排序，并且您决定通过一次交换两个盒子来对它们进行排序。 这样的交换需要的努力等于两个盒子重量的乘积。

目标是以最小的努力根据需要重新定位盒子。

输入
第一行由两个空格分隔的正整数组成，给出箱子的数量 (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）作为中介，可以获得进一步的减少。 如果我们用50（努力1000）交换20，然后用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

总共获得了 7600 的努力，而不是 8000 的努力，这是输出。

以上就是TCS_CODEVITA_QUESTION（需要解决方案）的详细内容，更多请关注php中文网其它相关文章！