← 返回题目列表

Codeforces · 2073/J

J. 聚集鲨鱼

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Gathering Sharks - 原题 PDF 第 1 页
原题PDF第19页
Gathering Sharks - 原题 PDF 第 2 页
原题PDF第20页
可复制的 PDF 提取文本
Problem J
                    Gathering Sharks
                     Time limit: 2 seconds


You are the leader of a swarm of n sharks living in a one-dimensional ocean. The sharks are positioned from left to
right, with each adjacent pair separated by a distance of one unit.

As the leader, you want all the sharks to gather at a common point to form a single group. Initially, no two sharks belong
to the same group; for each i = 1, . . . , n, the i-th shark from the left forms its own group, uniquely numbered ai,
consisting of only itself.

To achieve your goal, you can command the sharks to perform the following actions n −1 times.


   1. You shout out an integer b that meets both conditions:

           • There exists a group numbered b.

           • There exists at least one group numbered strictly smaller than b.

   2. Afterward, letting c be the largest existing group number strictly smaller than b, all the sharks in the group
     numbered b simultaneously move to the position of the group numbered c, and the two groups merge.

   3. The merged group is numbered b, and the group numbered c ceases to exist.


All sharks move at a constant speed of one unit distance per unit time. Commands must be executed sequentially, with
no overlap in execution. Once a command is completed, the next one can begin immediately.

Compute the minimum time required for all the sharks to gather at a common point by commanding the sharks n −1
times optimally.

Input

The first line of input contains an integer n (2 ≤n ≤500). The second line contains n pairwise distinct integers
a1, a2, . . . , an (1 ≤ai ≤n).

Output

Output the minimum time required for all the sharks to gather at a common point.


 Sample Input #1                          Sample Output #1
 4                                      4
 3 2 4 1


Explanation for the sample input/output #1

You can command the sharks to perform the following actions:

   1. You shout out 3. The leftmost shark moves to the position of the second-leftmost shark, and they form a group
     numbered 3. This takes 1 unit of time.



The 2025 ICPC Asia Pacific Championship Problem J: Gathering Sharks

2. You shout out 4. The second rightmost shark moves to the position of the group numbered 3, and they form a
     group numbered 4. This takes 1 unit of time.

   3. You shout out 4. The sharks in the group numbered 4 move to the rightmost position, forming a group of four
      sharks. This takes 2 units of time.

The total time is 1 + 1 + 2 = 4. It can be shown that 4 units of time is optimal.


 Sample Input #2                          Sample Output #2
 9                                      17
 1 2 4 5 7 8 3 6 9





The 2025 ICPC Asia Pacific Championship Problem J: Gathering Sharks