P4995.cpp

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    scanf("%d", &N);
    int stones[N]; // 每个石头的高度
    for (int i = 0; i < N; i++)
        scanf("%d", &stones[i]);
    sort(stones, stones + N); // 升序排，把高的石头放在末尾
    int front = 0, rear = N - 1;
    bool flag = true;     // 用于交替变更front和rear
    int currH = 0;        // 现在所在的高度
    long long result = 0; // 体力耗费
    while (front <= rear)
    {
        int targetH; // 跳到哪个高度的石头
        if (flag)
            targetH = stones[rear--];
        else
            targetH = stones[front++];
        int diff = targetH - currH;
        currH = targetH;
        result += diff * diff;
        flag = !flag;
    }
    printf("%lld", result);
    return 0;
}

/*
    这题是比较典型的贪心算法题，每一步要找到【和目前高度相差最远的】一块石头。

    整体的过程描述如下：
        最初主角位于地面，地面的高度为0:
        1. 先从地面跳到最高的一块石头 N 上
        2. 再从最高的一块石头跳到除地面外最低的石头 1 上
        3. 然后再从这个最低的石头 1 上跳到【第二最高的石头】 N-1 上
        4. 再从第二最高的石头跳到石头 2 上
        ...

    可以发现，当我【将表述所有石头的序列按高度进行排序】后，这个过程实际上做的就是“反复横跳”了，即：

    将石头序列按高度进行【升序】排序，在序列首个元素处置一个指针front，在最后一个元素处置一个指针rear，然后交替取front和rear对应的元素值，不断缩小[front,rear]区间，计算高度差并求和即可。

    注意本题的一个需要注意的点：

        * 输出的数值大小可能超过了整型所能表示的范围，因此需要使用long long类型对结果进行统计和储存。

        - SomeBottle 2023.3.17
*/

/*
# 跳跳！

## 题目描述

你是一只小跳蛙，你特别擅长在各种地方跳来跳去。

这一天，你和朋友小 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$。

## 输出格式

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

## 样例 #1

### 样例输入 #1

```
2
2 1
```

### 样例输出 #1

```
5
```

## 样例 #2

### 样例输入 #2

```
3
6 3 5
```

### 样例输出 #2

```
49
```

## 提示

#### 样例解释

两个样例按照输入给定的顺序依次跳上去就可以得到最优方案之一。

#### 数据范围
对于 $1 \leq i \leq n$，有 $0 < h_i \leq 10 ^ 4$，且保证 $h_i$ 互不相同。

对于 $10\%$ 的数据，$n \leq 3$；

对于 $20\%$ 的数据，$n \leq 10$；

对于 $50\%$ 的数据，$n \leq 20$；

对于 $80\%$ 的数据，$n \leq 50$；

对于 $100\%$ 的数据，$n \leq 300$。
*/