C. Coloring Game

C. Coloring Game

问题描述

Alice 和 Bob 正在使用一个大小为 $n$ 的整数数组 $a$ 玩一个游戏。

最初，数组的所有元素都是无色的。首先，Alice 选择 3 个元素并将它们涂成红色。然后 Bob 选择任意一个元素并将其涂成蓝色（如果它已经是红色的，则重新着色）。如果红色元素的总和严格大于蓝色元素的值，则 Alice 获胜。

你的任务是计算 Alice 可以选择 3 个元素以确保无论 Bob 的行动如何都能获胜的方法数。

第一行包含一个整数 $t$ $(1 \leq t \leq 1000)$ — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(3 \leq n \leq 5000)$ 。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 10^5)$ 。

输入的附加约束：所有测试用例的 $n$ 的总和不超过 5000。

对于每个测试用例，打印一个整数 — Alice 可以选择 3 个元素以确保无论 Bob 的行动如何都能获胜的方法数。

首先，按非递减顺序对数组 $a$ 进行排序。这确保了对于任意三个元素 $a_i, a_j, a_k$ （其中 $i < j < k$ ），我们有 $a_i \leq a_j \leq a_k$ 。

对于任意三个元素 $a_i, a_j, a_k$ （其中 $i < j < k$ ），如果满足以下条件，Alice 可以保证获胜：

$a_i + a_j > a_k$ （这确保了红色元素的总和严格大于蓝色元素）。这个条件处理了 Bob 选择最大元素 $a_k$ 作为蓝色元素的情况。
$a_i + a_j + a_k > a_n$ 。这确保了红色元素的总和严格大于数组中的最大元素 $a_n$ 。这个条件处理了 Bob 选择最大元素 $a_n$ 作为蓝色元素的情况。

只要满足这两个条件，Alice 就能保证无论 Bob 的选择如何都能获胜。

我们使用两个嵌套循环来遍历所有对 $a_i$ 和 $a_j$ ，并检查是否存在一个 $a_k$ 使得两个条件都满足。为了找到 $a_k$ ，我们可以使用二分搜索来找到满足条件的最大和最小的 $a_k$ 。