题目描述

如果您想练下英语的话，这里把英文问题描述放在这里。
当然您也可以直接跳到下面的题目翻译。

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: $400$ points

Problem Statement

Quickly after finishing the tutorial of the online game ATChat, you have decided to visit a particular place with $N − 1$ players who happen to be there.
These $N$ players, including you, are numbered $1$ through $N$, and the friendliness of Player $i$ is $A _ i$.

The $N$ players will arrive at the place one by one in some order.
To make sure nobody gets lost, you have set the following rule:

• Players who have already arrived there should form a circle, and a player who has just arrived there should cut into the circle somewhere.

When each player, except the first one to arrive, arrives at the place, the player gets comfort equal to the smaller of the friendliness of the clockwise adjacent player and that of the counter-clockwise adjacent player.
The first player to arrive there gets the comfort of $0$.

What is the maximum total comfort the $N$ players can get by optimally choosing the order of arrivals and the positions in the circle to cut into?

Constraints

• All values in input are integers.
• $2 \leq N \leq 2 \times 10 ^ 5$
• $1 \leq A_i \leq 10 ^ 9$

Input

Input is given from Standard Input in the following format:

$N$
$A _ 1, A _ 2 \ldots A _ N$

Output

Print the maximum total comfort the N players can get.

Sample Input 1

4
2 2 1 3

Sample Output 1

7

By arriving at the place in the order Player $4, 2, 1, 3,$ and cutting into the circle as shown in the figure, they can get the total comfort of $7$.

They cannot get the total comfort greater than $7$, so the answer is $7$.

Sample Input 2

7
1 1 1 1 1 1 1

Sample Output 2

6

题目翻译

不久，在完成了在线游戏 $ATChat$ 的教程后，你决定和 $N - 1$ 个碰巧在那里的人，去一个特别的地方。
包括你，一共 $N$ 个人，编号 $1 \sim N$，其中第 $i$ 个人的友好度为 $A _ i$。

这 $N$ 个人将按某种顺序依次到达那个地方，为了确保所有人都到齐了，你设立了如下规则：

• 已经到达那里的人应该形成一个圆圈，而刚刚到达那里的人应该从某个地方切入圆圈。

当每个人（第一个到达那里的人除外）到达了那里，他所得到的舒适度为他顺时针的下一个人和逆时针的下一个人的友好度的较小值。
第一个到达那里的人得到的舒适度为 $0$。

在到达顺序和切入圆圈的位置的最佳选择方案下，这 N 个人能的到的最大的舒适度和是多少？

数据范围

• 所有数都是整数
• $2 \leq N \leq 2 \times 10 ^ 5$
• $1 \leq A _ i \leq 10 ^ 9$

输入格式

输入由以下格式的标准输入给出:
$N$
$A _ 1\ \ A _ 2\ \ \ldots\ \ A _ N$

输出格式

输出这 $N$ 个人能得到的最大的舒适度和

输入样例 $1$

4
2 2 1 3

输出样例 $1$

7

样例 $1$ 解释

所有人按照 $4, 2, 1, 3$ 的顺序到达那里，并按如下图所示内容切入圆，他们可以得到 $7$ 的舒适度和。

他们不能够的到一个比 $7$ 更大的舒适度和，所以答案是 $7$。

输入样例 $2$

7
1 1 1 1 1 1 1

输出样例 $2$

6

算法

(贪心,排序,二叉堆) $\mathcal O(n \log n)$

这里先说做法，再给出证明。

做法

• 我们先将所有的 $A_i$ 从大到小排序。
  将排序后的第一个元素插入圆中。
• 对于后面的所有人，我们找一个左右两个端点的较小值小值最大的区间，并将这个人插入该区间。
  这样我们得到的插入顺序及插入位置即为最优解。

证明

• 对于第一次插入，我们得到的舒适度为 $0$
• 对于第二次插入，我们得到的舒适度为 $A_0$，也就是数组 $A$ 中的最大值。
  故不存在另一种插入方式，使得在第二次插入时，能得到更大的舒适度和。
• 对于第 $n$ 次插入，我们假设在前 $n = k$ 次插入时，得到的舒适度和为插入 $k$ 次的最大舒适度和。
  那么在第 $n = k + 1$ 次插入时，由于我们是通过枚举，找到了所有区间中左右端点的最小值最大的一个区间，将这个数插入进去的，所以我们第 $k + 1$ 次插入时得到的舒适度为最大的舒适度。
  而在插入前 $k$ 次时，我们得到了最大的舒适度和，所以在第 $n = k + 1$ 次插入时，我们得到的舒适度和也为最大舒适度和。
• 故在所有元素都插入完后，也就是第 $N$ 次插入后，我们得到的舒适度和为最大舒适度和。

当然，我们这么直接枚举圆上的所有区间肯定是不行的，时间复杂度会退化到 $\mathcal O(n ^ 2)$。
我们需要一种数据结构，能支持快速的插入、弹出、查询最大值操作。用大根堆即可。
然后我们需要考虑我们每次插入的元素和删除的元素分别是什么。
我们每次删除的元素很好考虑，就是堆中的最大元素，即删除堆顶。
而每次插入元素，相当于是把当前区间划分为了两个最小左右端点值为 $A _ i$的区间，所以我们要在堆中插入两个 $A _ i$。

这样时间复杂度就降到了 $\mathcal O(n \log n)$，可以接受。

时间复杂度

首先将数组 $A$ 排序，时间复杂度为 $\mathcal O(n \log n)$，
我们一共要在堆中插入 $2n$ 次元素，删除 $n$ 次元素，时间复杂度为 $\mathcal O(3n \log (3n))$，
忽略常数，总的时间复杂度为 $\mathcal O(n \log n)$。

$C ++ $ 代码

#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;
const int N = 200005;

int n;    // 即上述 N
ll ans;   // 存答案
int A[N]; // 即上述数组 A


int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", A + i);

    sort(A, A + n);    // 先将 A 从小到大排序
    reverse(A, A + n); // 再将 A 翻转一下，得到从大到小排序的序列

    priority_queue<int> heap; // 直接用 STL 的大根堆（STL 万岁！！！）
    heap.push(A[0]);          // 在堆中插入第一个元素

    for (int i = 1; i < n; i ++ ) // 从 1 到 n 循环 n - 1 次
    {
        ans += heap.top(), heap.pop();    // 将堆顶元素假如答案中，并弹出
        heap.push(A[i]), heap.push(A[i]); // 在堆中插入两遍 A[i]
    }
    printf("%lld\n", ans);    // 输出 ans
    return 0;
}