跳跳！

题意

有 n 块高度互不相同的石头，地面高度为 0。从高度 x 跳到高度 y 的体力是 (x-y)^2。要把每块石头恰好跳一次，最后停在任意石头上，求最大总耗费。

思路

体力是高度差的平方，高度差越大收益越大。因此应该让跳跃顺序尽量在高低两端之间来回切换。

把高度排序后：

第一跳从地面 0 到最高石头，收益最大；
接下来从最高跳到最低；
再从最低跳到次高；
再从次高跳到次低；
如此交替，直到所有石头都跳完。

用双指针实现：right 指向当前最高，left 指向当前最低。每轮先跳 right，再跳 left。

样例 6 3 5 排序后是 3 5 6：

跳跃	高度变化	体力
1	`0 -> 6`	36
2	`6 -> 3`	9
3	`3 -> 5`	4
合计		49

Python 知识

diff * diff 比 diff ** 2 更贴近竞赛里“平方”的写法，也避免浮点参与。
Python int 不会像 C++ int 一样溢出，但仍要保持线性计算。
双指针每跳到一块石头，就移动对应端点。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    heights = data[1:1 + n]
    heights.sort()

    left = 0
    right = n - 1
    current = 0
    answer = 0

    while left <= right:
        diff = heights[right] - current
        answer += diff * diff
        current = heights[right]
        right -= 1

        if left > right:
            break

        diff = heights[left] - current
        answer += diff * diff
        current = heights[left]
        left += 1

    print(answer)


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P4995 跳跳！ */
/* 排序后交替跳最高和最低，让相邻高度差尽量大。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;

int n;
int h[MAXN]; // 石头高度

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    // 高度排序
    sort(h + 1, h + n + 1);

    int left = 1, right = n;
    int cur = 0; // 当前所在高度，从地面 0 开始
    long long ans = 0;

    while (left <= right) {
        // 跳到当前最高的石头
        long long diff = h[right] - cur;
        ans += diff * diff;
        cur = h[right];
        right--;

        if (left > right) break;

        // 跳到当前最低的石头
        diff = h[left] - cur;
        ans += diff * diff;
        cur = h[left];
        left++;
    }

    cout << ans << "\n";
    return 0;
}

复杂度

排序复杂度是 $O(n \log n)$ ，跳跃模拟是 $O(n)$ 。

空间复杂度是 $O(n)$ 。

总结

这题不是模拟任意跳法，而是利用平方函数偏爱大差值的特点，让跳跃顺序在当前最高和当前最低之间交替。

目录

题意

思路

Python 知识

代码

复杂度

总结