【题目来源】
洛谷：P4995 跳跳！ - 洛谷
【题目描述】
你是一只小跳蛙，你特别擅长在各种地方跳来跳去。
这一天，你和朋友小 F 一起出去玩耍的时候，遇到了一堆高矮不同的石头，其中第 \(i\) 块的石头高度为 \(h_i\)，地面的高度是 \(h_0=0\)。你估计着，从第 \(i\) 块石头跳到第 \(j\) 块石头上耗费的体力值为 \((h_i-h_j)^2\)，从地面跳到第 \(i\) 块石头耗费的体力值是 \((h_i)^2\)。
为了给小 F 展现你超级跳的本领，你决定跳到每个石头上各一次，并最终停在任意一块石头上，并且小跳蛙想耗费尽可能多的体力值。
当然，你只是一只小跳蛙，你只会跳，不知道怎么跳才能让本领更充分地展现。
不过你有救啦！小 F 给你递来了一个写着 AK 的电脑，你可以使用计算机程序帮你解决这个问题，万能的计算机会告诉你怎么跳。
那就请你——会写代码的小跳蛙——写下这个程序，为你 NOIP AK 踏出坚实的一步吧！
【输入】
输入一行一个正整数 \(n\)，表示石头个数。
输入第二行 \(n\) 个正整数，表示第 i 块石头的高度 \(h_i\)。
【输出】
输出一行一个正整数，表示你可以耗费的体力值的最大值。
【输入样例】
2
2 1
【输出样例】
5
【解题思路】
【算法标签】
《洛谷 P4995 跳跳》 #贪心# #排序# #洛谷月赛#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 点的数量
// a[305]: 存储所有点的坐标
// l, r: 左右指针
// mark: 标记当前选择左还是右
// tmp: 记录上一个选择的点坐标
// ans: 存储最终结果（距离平方和）
int n, a[305], l, r, mark = 1, tmp;
long long ans = 0;int main()
{// 输入点的数量ncin >> n;// 输入所有点的坐标for (int i = 1; i <= n; i++){cin >> a[i];}// 对点坐标进行排序sort(a + 1, a + n + 1);// 初始化左右指针l = 0;r = n;tmp = 0; // 初始位置设为0// 交替选择左右两端的点while (l <= r){if (mark == 1) // 选择右侧的点{// 计算当前点与上一个点的距离平方并累加ans += (a[r] - tmp) * (a[r] - tmp);l++; // 左指针右移tmp = a[r]; // 更新上一个点的位置mark = 0; // 下次选择左侧}else // 选择左侧的点{// 计算当前点与上一个点的距离平方并累加ans += (a[l] - tmp) * (a[l] - tmp);r--; // 右指针左移tmp = a[l]; // 更新上一个点的位置mark = 1; // 下次选择右侧}}// 输出最终的距离平方和cout << ans << endl;return 0; // 程序正常结束
}
【运行结果】
2
2 1
5