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


可复制的 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