← 返回题目列表

Codeforces · 2156/E

E. 买卖股票的最佳时机

中文机器翻译题面 查看原题

的 美女 长度为 $$$m$$$(其中 $$$m \ge 2$$$)的数组 $$$b$$$ 的 被定义为所有索引对 $$$i$$$ 和 $$$j$$$ 上 $$$b_j - b_i$$$ 的最大值,使得 $$$1\le i \lt j\le m$$$。更正式地说,它等于 $$$\max\limits_{1\le i \lt j\le m} (b_j - b_i)$$$。请注意,如果数组严格递减,则美观度可能为负。

hao 和 Alex 在长度为 $$$n$$$ 的数组 $$$a$$$ 上玩回合制游戏。最初,数组的所有元素都被解锁。选手们轮流轮流, 郝先行.

  • 轮到Hao了,他从数组$$$a$$$中选择一个未锁定的元素并将其删除。
  • 轮到 Alex 时,他从数组 $$$a$$$ 中选择一个未锁定的元素并将其锁定(因此Hao 无法再将其删除)。

游戏继续进行,直到 $$$a$$$ 的所有元素都被锁定或删除。可以证明,游戏持续了$$$n$$$个回合,并且$$$\left\lfloor \frac{n}{2} \right\rfloor$$$元素最终将保持锁定在数组$$$a$$$中。

Hao 希望最小化最终锁定元素数组的美感,而 Alex 希望最大化它。如果两名球员都发挥最佳,则确定最终阵容的美观程度。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4\le n\le 10^5$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果Hao 和Alex 都发挥最佳,则输出一个表示最终数组的美丽程度的整数。

示例

输入
复制

6
5
5 1 2 3 4
4
3 1 2 1
10
7 1 3 5 8 2 8 3 5 1
6
1 1 4 5 1 4
9
9 9 8 2 4 4 3 5 3
4
1000000000 1 2 3

输出
复制

1
-2
5
3
1
-999999998

注意

在第一个测试用例中,游戏可以如下进行。 粗体元素 被 Alex 锁定:

  • 第 1 回合(Hao):删除元素 $$$1$$$(位置 $$$2$$$),得到 $$$[5, 2, 3, 4]$$$。
  • 第 2 回合 (Alex):锁定元素 $$$3$$$(位于 $$$3$$$ 位置),结果为 $$$[5, 2, \mathbf{3}, 4]$$$。
  • 第3回合(Hao):删除元素$$$2$$$(位于$$$2$$$位置),得到$$$[5, \mathbf{3}, 4]$$$。
  • 第4回合(Alex):锁定元素$$$4$$$(位于$$$3$$$位置),导致$$$[5, \mathbf{3}, \mathbf{4}]$$$。
  • 第5回合(Hao):删除元素$$$5$$$(位置$$$1$$$),得到$$$[\mathbf{3}, \mathbf{4}]$$$。

最终数组 $$$b = [3, 4]$$$ 等于 $$$b_2 - b_1 = 4 - 3 = 1$$$。

在第二个测试用例中,请注意答案可能是否定的:

  • 第 1 回合(Hao):删除元素 $$$2$$$(位置 $$$3$$$),得到 $$$[3, 1, 1]$$$。
  • 第 2 回合 (Alex):锁定元素 $$$1$$$(位于 $$$2$$$ 位置),结果为 $$$[3, \textbf{1}, 1]$$$。
  • 第3回合(Hao):删除元素$$$1$$$(位置$$$3$$$),得到$$$[3, \textbf{1}]$$$。
  • 第4回合(Alex):锁定元素$$$3$$$(位于$$$1$$$位置),导致$$$[\textbf{3}, \textbf{1}]$$$。

最终数组 $$$b = [3, 1]$$$ 等于 $$$b_2 - b_1 = 1 - 3 = -2$$$。

在第三个测试用例中,一个可能的最终数组(假设两个玩家都最佳发挥)是 $$$b = [3, 5, 8, 5, 1]$$$。美丽之处在于,所有索引对 $$$i$$$ 和 $$$j$$$ 之间的最大差异 $$$b_j - b_i$$$ 使得 $$$1\le i \lt j\le 5$$$ 等于 $$$b_3 - b_1 = 8 - 3 = 5$$$。