小跳蛙 解题思路

quanjun · 2026-02-10 09:21:37 · 学习·文化课

核心思路

贪心。

先给 h 数组从小到大排个序。

贪心的思路就是排序后按照以下方式移动：

也就是说：

• 如果我当前在左端点，我应该跳到（没走到过的最）右端点；
• 如果我当前在右端点，我应该跳到（没走到过的最）左端点。

实现代码如下：

示例程序

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
long long h[maxn], ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    sort(h+1, h+n+1);
    for (int i = 0, j = n, k = 0; i < j; k ^= 1) {
        ans += (h[i] - h[j]) * (h[i] - h[j]);
        k ? j-- : i++;
    }
    cout << ans << endl;
    return 0;
}

这里，我用：

• 变量 i 表示左端点的编号；
• 变量 j 表示右端点的编号；
• 变量 k 表示我当前在左端点还是右端点：
  • 如果 k = 0 表示我当前在左端点 i 准备跳到右端点 j；
  • 如果 k = 1 表示我当前在右端点 j 准备跳到左端点 i。

无论我当前在左端点还是右端点，跳一次的代价都是 (h_i - h_j)^2。

当时：

• 如果从左端点 i 跳到右端点 j，跳过去之后（因为不会再到 i 了，所以）i++
• 如果从右端点 j 调到左端点 i，跳过去之后（因为不会再到 j 了，所以）j--

然后 k 每一异或 1，是为了让 k 在 0 \leftrightarrow 1 之间切换