洛谷 P4995：跳跳！ ← 贪心算法

【题目来源】
https://www.luogu.com.cn/problem/P4995

【题目描述】
你是一只小跳蛙，你特别擅长在各种地方跳来跳去。
这一天，你和朋友小 F 一起出去玩耍的时候，遇到了一堆高矮不同的石头，其中第 i 块的石头高度为 hi，地面的高度是 h0=0。你估计着，从第 i 块石头跳到第 j 块石头上耗费的体力值为 (hi-hj)^2，从地面跳到第 i 块石头耗费的体力值是 (hi)^2。
为了给小 F 展现你超级跳的本领，你决定跳到每个石头上各一次，并最终停在任意一块石头上，并且小跳蛙想耗费尽可能多的体力值。
当然，你只是一只小跳蛙，你只会跳，不知道怎么跳才能让本领更充分地展现。
不过你有救啦！小 F 给你递来了一个写着 AK 的电脑，你可以使用计算机程序帮你解决这个问题，万能的计算机会告诉你怎么跳。
那就请你——会写代码的小跳蛙——写下这个程序，为你 NOIP AK 踏出坚实的一步吧！

【输入格式】
输入一行一个正整数 n，表示石头个数。
输入第二行 n 个正整数，表示第 i 块石头的高度 hi。

【输出格式】
输出一行一个正整数，表示你可以耗费的体力值的最大值。

【输入样例1】
2
2 1

【输出样例1】
5

【输入样例2】
3
6 3 5

【输出样例2】
49

【数据范围】
对于 1≤i≤n，有 0<hi≤10^4，且保证 hi 互不相同。
对于 10% 的数据，n≤3；
对于 20% 的数据，n≤10；
对于 50% 的数据，n≤20；
对于 80% 的数据，n≤50；
对于 100% 的数据，n≤300。

【算法分析】
本题思路就是排序后贪心：对于数量任意的柱子，应从先从地面跳到最高柱子，再跳到最低柱子，再跳到次高柱子……依次类推。
本质上，是让小青蛙每次跳到和自己当前位置高度差最大的柱子上。

【算法代码】

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

const int maxn=305;
long long h[maxn];
long long ans;

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

    int le=0,ri=n;
    while(le<ri) {
        ans+=pow(h[ri]-h[le],2);
        le++;
        ans+=pow(h[ri]-h[le],2);
        ri--;
    }

    cout<<ans<<endl;

    return 0;
}

/*
in:
3
6 3 5

out:
49
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/P4995