跳跳！

题目解析

直觉:

存在一种排序,使得能得到最值
h0排在开头
1. 直觉选接下来选最高的 $h_n$ ,因为这样 $(h_n - 0)^2$ 是最大的
2. 问题变成, $h_n$ 排在开头,这显然是一种递归,选最低的元素
3. 每次选择为候选中固定选一种,是贪心

这也是一道非常经典的贪心算法题目，和上一道“看电视”的题目一样，核心都在于找到最优的策略。

1. 核心分析：为什么要“反复横跳”？

题目要求最大化耗费的体力值，体力值的计算公式是 $(h_i - h_j)^2$ 。

这是一个平方函数。我们知道， $y = x^2$ 的图像是一个开口向上的抛物线， $x$ 的绝对值越大， $y$ 的值增长得越快。

也就是说，为了让 $(h_i - h_j)^2$ 最大，我们需要让高度差 $|h_i - h_j|$ 尽可能大。

贪心策略如下：

第一步：你站在地面（高度 0）。为了让第一跳的代价最大，你应该跳到最高的那块石头上。
第二步：你现在站在最高的石头上。为了让下一跳代价最大，你应该跳到最低的那块石头上（因为最高减最低，差值最大）。
第三步：你现在站在最低的石头上。剩下的石头里，离你最远的是第二高的石头。
第四步：跳到第二低的石头。
…以此类推。

形象的理解：

这就好比在一个排序后的数组上进行“钟摆运动”或“反复横跳”：

地面(0) -> 最大 -> 最小 -> 次大 -> 次小 -> …

2. 算法流程

排序：将所有石头的高度从小到大排序。
双指针：
- 左指针 L 指向数组最左端（最小值）。
- 右指针 R 指向数组最右端（最大值）。
- 记录当前所在位置的高度 current，初始为 0。
交替跳跃：
- 只要还有石头没跳过（L <= R）：
  - 先跳到最大（R指向的石头）：计算 (h[R] - current)^2 加到总和里，更新 current = h[R]，然后 R--。
  - 如果石头跳完了，结束循环。
  - 再跳到最小（L指向的石头）：计算 (h[L] - current)^2 加到总和里，更新 current = h[L]，然后 L++。

3. 复杂度分析

时间复杂度：主要是排序，为 $O(N \log N)$ 。 $N \le 300$ ，这在计算机里是一瞬间的事。
空间复杂度： $O(N)$ 存储石头高度。

4. 坑点提示 (重要)

虽然 $N$ 很小，但请注意数据范围：

$h_i \le 10^4$ 。
单次跳跃最大代价约为 $(10^4)^2 = 10^8$ 。
总共有 300 次跳跃，极限总和约为 $300 \times 10^8 = 3 \times 10^{10}$ 。

注意：C++ 中 int 的最大值约为 $2 \times 10^9$ 。计算结果会爆 int！

解决：统计答案的变量必须使用 long long。

5. 参考代码 (C++)

cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

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

    // 1. 排序
    sort(h.begin(), h.end());

    // 2. 双指针初始化
    int l = 0;          // 左指针（最小）
    int r = n - 1;      // 右指针（最大）
    int current = 0;    // 当前高度（初始为地面 0）
    long long ans = 0;  // 必须用 long long，否则会溢出

    // 3. 开始反复横跳
    while (l <= r) {
        // 第一跳：跳向当前最大的 (r)
        ans += (long long)(h[r] - current) * (h[r] - current);
        current = h[r];
        r--; // 右边那个石头踩过了，指针左移

        // 检查是否跳完
        if (l > r) break;

        // 第二跳：跳向当前最小的 (l)
        ans += (long long)(h[l] - current) * (h[l] - current);
        current = h[l];
        l++; // 左边那个石头踩过了，指针右移
    }

    cout << ans << endl;

    return 0;
}

证明

显然: 不证明贪心的正确性,总感觉怪怪的，“不仅知其然，还要知其所以然” 是非常重要的品质。

证明贪心算法的正确性通常有两种方法：

“交换论证法”（Exchange Argument）
“数学不等式法”。

对于这道题，我们可以用代数变形配合**排序不等式（Rearrangement Inequality）**的逻辑来证明。

排序不等式

这是一个非常棒的数学问题！排序不等式 (Rearrangement Inequality) 是高中数学竞赛和 ACM 算法竞赛中处理“最值问题”的一把利器。

既然你已经能熟练使用 C++ 和算法，我们可以用代数推导和直观逻辑两种方式来彻底搞定它。

1. 什么是排序不等式？

假设有两个长度为 $n$ 的序列，我们把它们从小到大排好序：

$a_1 \le a_2 \le \dots \le a_n$
$b_1 \le b_2 \le \dots \le b_n$

我们将这两个序列中的数字两两配对相乘，然后求和。会有三种典型的情况：

同序和 (Sequential Sum)：大的配大的，小的配小的。

$S_{max} = a_1b_1 + a_2b_2 + \dots + a_nb_n$
乱序和 (Random Sum)：随意打乱顺序配对。

$S_{random} = a_1b_{p_1} + a_2b_{p_2} + \dots + a_nb_{p_n}$
(其中 $p$ 是 $1 \dots n$ 的一个随机排列)
反序和 (Reversed Sum)：最大的配最小的，最小的配最大的。

$S_{min} = a_1b_n + a_2b_{n-1} + \dots + a_nb_1$

排序不等式的结论是：

\text{同序和} \ge \text{乱序和} \ge \text{反序和}

\sum_{i=1}^n a_i b_i \ge \sum_{i=1}^n a_i b_{p_i} \ge \sum_{i=1}^n a_i b_{n-i+1}

简单记忆：

想求最大值：这就叫“强强联合”。

想求最小值：这就叫“损耗最大化”（或者上一题里的“为了让差值项最小”）。

2. 直观证明（生活中的例子）

想象你有两堆东西：

钱堆：有一张 10元，有一张 100元。 (即 $a_1=10, a_2=100$ )
倍数卡：有一张 x1卡，有一张 x10卡。 (即 $b_1=1, b_2=10$ )

你也只有两种搭配方法：

方案 A（同序 - 强强联合）：

100元 $\times$ 10倍 = 1000
10元 $\times$ 1倍 = 10
总和 = 1010

方案 B（反序 - 强弱搭配）：

100元 $\times$ 1倍 = 100
10元 $\times$ 10倍 = 100
总和 = 200

道理很明显：既然你有“放大器”（倍数卡），你肯定希望那个最大的放大器去放大那个本来就最大的数。把超级放大器用在小树苗上是浪费，用在参天大树上才能获得最大收益。

3. 严格数学证明（微扰分析法 / Exchange Argument）

在算法证明中，我们常用**“微扰分析”**（假如我不按规矩来，结果会不会变差？）来证明贪心策略。

我们只需要证明 $n=2$ 的情况，所有 $n>2$ 的情况都可以分解为无数次 $n=2$ 的交换。

设定：

已知 $a_1 < a_2$ 且 $b_1 < b_2$ 。

对比：

同序和： $S_1 = a_1b_1 + a_2b_2$
反序和： $S_2 = a_1b_2 + a_2b_1$

我们要证明 $S_1 > S_2$ 。

作差法证明：

S_1 - S_2 = (a_1b_1 + a_2b_2) - (a_1b_2 + a_2b_1)

重新组合各项（合并同类项）：

= a_2b_2 - a_2b_1 - a_1b_2 + a_1b_1

= a_2(b_2 - b_1) - a_1(b_2 - b_1)

提取公因式 $(b_2 - b_1)$ ：

= (a_2 - a_1)(b_2 - b_1)

分析符号：

因为我们设定了 $a_1 < a_2$ ，所以 $(a_2 - a_1)$ 是正数。
因为我们设定了 $b_1 < b_2$ ，所以 $(b_2 - b_1)$ 是正数。
正数乘以正数，结果恒为正数。

结论：

S_1 - S_2 > 0 \implies S_1 > S_2

即：同序和 > 反序和。

对于任意乱序的情况，只要我们发现有一对下标 $i, j$ 是“逆序”的（即大的配了小的），我们就可以交换它们的配对对象。根据上面的证明，每次交换都会让总和变大。直到所有配对都变成“同序”，总和就达到了最大值。

根据上面两对元素的性质,可以想到

设最大乘积和X : $(a_i,b_k),\cdots$
- 按 $a_i$ 从小到大排列,那么可以使用反证法,把最大的 $b_n$ 移动到与 $a_1$ 配对
- 递归, 去除 $(a_1,b_n)$ ,变成类一个类似的问题,使用同样的方法

4. 回到“小跳蛙”题目

在上一题《跳跳！》中，我们的目标是让 $S = \sum (h_i - h_{next})^2$ 最大。

展开后其中有一项是减去交叉项： $- 2 \sum h_i h_{next}$ 。

我们要让整个式子最大，就要让被减去的这一项最小。
根据排序不等式，要让乘积和最小，必须是反序和。
也就是：序列中最大的数，必须和序列中最小的数相乘（相邻）。

这就是为什么我们要把石头排序后，用“最大配最小”的方式来安排跳跃顺序。

5. 总结

同序和最大（ $a \uparrow, b \uparrow$ ）：想要最大收益，好马配好鞍。
反序和最小（ $a \uparrow, b \downarrow$ ）：想要最小代价（或最小化某个中间项），好马配劣鞍。

这个数学原理是很多贪心算法（比如“排队打水问题”、“最小生成树的某些性质”）的基石。

经典的 “排队接水问题”,就是使用的排序不等式

严格证明1: 不等式法

1. 直观理解：为什么要“一大一小”？

首先，回顾一下体力公式： $(h_i - h_j)^2$ 。

这是一个凸函数（Convex Function）。它的特性是：距离越大，收益呈爆炸式增长。

距离为 2，收益 $2^2 = 4$
距离为 4，收益 $4^2 = 16$ （距离翻倍，收益变为 4 倍）
距离为 10，收益 $10^2 = 100$

直觉：为了总和最大，我们要尽量避免“小碎步”，而要尽可能多地制造“大跨步”。如果你在低处，就要往最高跳；如果你在高处，就要往最低跳。

2. 严格证明（代数推导）

假设我们的跳跃序列是 $P_0, P_1, P_2, \dots, P_n$ ，其中 $P_0 = 0$ （地面）， $P_1 \dots P_n$ 是石头高度的一个排列。

我们要最大化总消耗 $S$ ：

S = \sum_{i=0}^{n-1} (P_i - P_{i+1})^2

我们将平方项展开：

(P_i - P_{i+1})^2 = P_i^2 + P_{i+1}^2 - 2 P_i P_{i+1}

把所有项加起来：

S = (P_0^2 + P_1^2 + \dots + P_{n-1}^2) + (P_1^2 + P_2^2 + \dots + P_n^2) - 2 \sum_{i=0}^{n-1} P_i P_{i+1}

整理一下，注意到中间的项 $P_1 \dots P_{n-1}$ 被加了两次（作为起点一次，作为终点一次），而 $P_0$ 和 $P_n$ 只加了一次：

S = P_0^2 + P_n^2 + 2 \sum_{i=1}^{n-1} P_i^2 - 2 \sum_{i=0}^{n-1} P_i P_{i+1}

因为 $P_0 = 0$ ，且 $P_1 \dots P_n$ 是固定的石头高度集合。要让 $S$ 最大，我们需要关注两点：

第一点：让平方和部分最大化

2 \sum_{i=1}^{n-1} P_i^2 + P_n^2

这一项里，中间的石头贡献了 $2$ 倍的平方值，而最后一个石头 $P_n$ 只贡献了 $1$ 倍。

为了让总和最大，我们希望数值大的石头都在中间被反复踩（贡献2倍），而数值小的石头或者中等石头做结尾（贡献1倍）。

贪心策略的做法：先跳最大的，再跳最小的，再跳次大的……这样最大的那些石头肯定会被当作“中间跳板”，贡献 $2 \times h^2$ 。最后停下来的往往是中间大小的石头。符合最大化要求。

第二点：让交叉项最小化 (核心)

这是决定性的一步。我们要最大化 $S$ ，也就是要最小化减去的那部分：

\text{目标：最小化 } \sum_{i=0}^{n-1} P_i P_{i+1}

这是一个经典的**“排序不等式”**变体。

原理：要让两个数的乘积之和最小，应该用**“最小的数”乘以“最大的数”**。

(例如：有数 1, 10, 20。组合 $1\times20 + 10$ 比 $1\times10 + 20$ 小)。

在我们的序列中， $P_i$ 和 $P_{i+1}$ 是相邻的两个跳跃点。为了让它们的乘积和最小，我们需要让相邻的两个高度差尽可能大（即一个很大，一个很小）。

贪心策略的做法：
- 序列： $0 \to \text{Max} \to \text{Min} \to \text{Second Max} \dots$
- 相邻对： $(0, \text{Max})$ , $(\text{Max}, \text{Min})$ , $(\text{Min}, \text{Second Max}) \dots$
- 你看，每一对都是当前可用的极小值配对极大值。这正是让乘积项 $\sum P_i P_{i+1}$ 最小化的最优排列方式。

3. 举个简单的例子验证

假设石头高度是 $h = \{10, 20\}$ ，地面 0。

方案 A（贪心：反复横跳）：

$0 \to 20 \to 10$

消耗： $(20-0)^2 + (10-20)^2 = 400 + 100 = \mathbf{500}$
交叉项乘积： $0\times20 + 20\times10 = 200$ （较小）

方案 B（顺着跳）：

$0 \to 10 \to 20$

消耗： $(10-0)^2 + (20-10)^2 = 100 + 100 = 200$
交叉项乘积： $0\times10 + 10\times20 = 200$
等等，为什么交叉项一样？

因为在这个短例子里，中间项 $10$ 和 $20$ 的位置决定了平方和贡献。
- 方案 A 中间项是 20（最大值），贡献 $2 \times 20^2 + 10^2 = 900$ 。
- 方案 B 中间项是 10（最小值），贡献 $2 \times 10^2 + 20^2 = 600$ 。
- 显然方案 A 赢在“把大数放在中间”。

方案 C（乱跳，如果 $N$ 更多）：

假设 $h=\{1, 100\}$ 。

贪心 $0 \to 100 \to 1$ ：代价 $10000 + 9801 \approx 19801$ 。
顺跳 $0 \to 1 \to 100$ ：代价 $1 + 9801 \approx 9802$ 。
这里贪心赢在交叉项最小化： $(0\times100 + 100\times1)$ 远小于 $(0\times1 + 1\times100)$ 。

总结

贪心策略之所以正确，是因为它同时做到了两件事：

让大数贡献更多：最大的那些石头被安排在路径中间，被计算了两次平方和。
让相邻差最大：通过“极大配极小”，最小化了 $P_i P_{i+1}$ 这个减分项。

这就是为什么你要像青蛙一样“反复横跳”的原因！

严格证明2: 交换验证

参考: https://www.luogu.com.cn/article/y9wvbuth

这个证明确实更直观，而且它用到了贪心算法证明皇冠上的明珠——交换论证法（Exchange Argument），有时候也叫微扰法。

你截图中的这个证明方法，其实比刚才讲的“排序不等式”更具普适性，因为它不需要把整个公式展开，而是直接从路径的角度去思考。

我们来拆解一下这个证明的精髓，看看它是如何通过“交换”把非最优解变成最优解的。

核心逻辑：反证法 + 交换论证

假设：存在一种“最优策略”，它的第一步不跳到最高的 $h_n$ ，而是跳到了某个中间的石头 $h_p$ 。

目标：证明如果这样做，我们总能找到一种改法，让总消耗体力变得更大。这就说明刚才的假设不是最优的。

证明分了两种情况，非常有条理：

情况 1： $h_n$ 是终点 (简单情况)

原来的走法： $0 \to h_p \dots \to h_n$ （结束）
改进的走法： $0 \to h_n \dots \to h_p$ （相当于把整个路程反过来走）
比较：
- 原来的第一步消耗： $h_p^2$
- 现在的第一步消耗： $h_n^2$
- 因为 $h_n > h_p$ ，显然 $h_n^2 > h_p^2$ 。
结论：改完后体力消耗更大，所以第一步必须跳 $h_n$ 。

情况 2： $h_n$ 不是终点 (精彩部分)

这是图中最核心的逻辑。

原来的走法： $0 \to h_p \dots \dots h_n \to h_q$
- 意思是你第一步跳到了 $p$ ，中间经过一堆乱七八糟的跳跃，跳到了最高的 $n$ ，然后从 $n$ 跳去了 $q$ 。
改进的走法： $0 \to h_n \dots \dots h_p \to h_q$
- 怎么改的？ 这是一个经典的**“路径翻转”**操作。
- 把 $0$ 直接连到 $h_n$ 。
- 把 $h_p$ 到 $h_n$ 之间的路径全部反向（翻转）。注意，石头之间的距离是绝对值， $(a-b)^2 = (b-a)^2$ ，所以路径中间反过来走，体力消耗是不变的。
- 最后从 $h_p$ 连到 $h_q$ 。

算账（核心不等式）：

我们要比较只发生变化的这两根“连接线”：

新路径增量： $h_n^2$ (第一跳) + $(h_p - h_q)^2$ (翻转后的最后一跳)
旧路径增量： $h_p^2$ (第一跳) + $(h_n - h_q)^2$ (中间那一跳)

做差（新 - 旧）：

\Delta = [h_n^2 + (h_p - h_q)^2] - [h_p^2 + (h_n - h_q)^2]

展开化简（就像图里写的那样）：

\Delta = h_n^2 + h_p^2 - 2h_ph_q + h_q^2 - h_p^2 - (h_n^2 - 2h_nh_q + h_q^2)

消掉 $h_n^2, h_p^2, h_q^2$ 后，只剩下：

\Delta = -2h_ph_q + 2h_nh_q = 2h_q(h_n - h_p)

分析结果：

$h_q > 0$ （因为是正整数高度）
$h_n - h_p > 0$ （因为 $n$ 是最高的， $p$ 是矮的）
所以 $\Delta > 0$ 。

结论：新的走法比所谓的“最优解”消耗还要大！这说明假设错误，第一步必须跳到 $h_n$ 。

为什么说这个证明“更好”？

它不需要数学“巧合”：刚才的排序不等式证明依赖于公式展开后的交叉项恰好符合形式。而这个证明利用的是图论的思想（路径翻转）。
通用性强：这种“翻转一段路径”的操作，是解决 TSP（旅行商问题） 等复杂图论问题中常用的 2-opt 优化算法 的核心思想。你现在理解了这个，以后学高级算法会非常快。
构造性：它不仅告诉你答案是对的，还通过构造过程（怎么翻转路径）让你看到了为什么原来的不够好。

总结：

只要能证明“我稍微换一下顺序，结果会更好”，就能证明贪心策略的正确性。

这一招在很多题目里都能用，比如经典的**“国王游戏”**（NOIP题），也是用这种相邻交换法证明的

目录