题目回顾（原题：Tender Carpenter）

给定一个数组 $a_1, a_2, \dots, a_n$。
一个整数集合 $S$ 是稳定的，当且仅当：从 $S$ 中任意选取三个数 $u, v, w$（可以重复）作为边长，都能构成一个非退化三角形。

非退化三角形的条件是：

$$x + y > z,\quad y + z > x,\quad z + x > y$$

要求将数组划分成若干个连续非空子段，使得每个子段内所有元素构成的集合都是稳定的。
问：是否存在至少两种不同的划分方式？

---

核心数学结论

引理 1：稳定集合的等价条件

一个集合 $S$ 是稳定的 当且仅当 以下条件成立：

$$2 \cdot \min(S) > \max(S)$$

证明：

• 必要性：如果 $2 \cdot \min(S) \le \max(S)$，取 $x = \min(S)$，$y = \min(S)$，$z = \max(S)$，则 $x + y = 2 \cdot \min(S) \le \max(S) = z$，不满足三角不等式，矛盾。

• 充分性：如果 $2 \cdot \min(S) > \max(S)$，则对任意 $x, y, z \in S$，有：

  $$x + y \ge 2 \cdot \min(S) > \max(S) \ge z$$

  同理可证其他两个不等式，因此三角不等式全部成立。

---

转化为数组划分问题

对于一个连续子段 $a[l..r]$，设：

$$m = \min(a[l..r]), \quad M = \max(a[l..r])$$

该子段稳定 $\iff$ $2m > M$。

---

最少划分方式分析

基础划分

划分一：每个元素单独成段。

• 单元素集合 $\{a_i\}$ 显然稳定（因为只能选三个相同的数 $a_i, a_i, a_i$，满足 $a_i + a_i > a_i$）。

因此，至少存在一种划分方式（每个元素单独成段）。

寻找第二种划分

如果存在另一种不同的划分方式，则必须满足：存在某个长度 $\ge 2$ 的子段是稳定的，并且剩余部分也能划分成稳定段。

---

关键定理

定理：存在至少两种不同划分方式 当且仅当 存在至少一个 $i$（$1 \le i < n$）使得：

$$2 \cdot \min(a_i, a_{i+1}) > \max(a_i, a_{i+1})$$

证明：

充分性：若存在这样的 $i$，则：

• 划分一：$[a_1], [a_2], \dots, [a_n]$
• 划分二：将 $a_i$ 和 $a_{i+1}$ 合并成一个子段 $[a_i, a_{i+1}]$，其余元素单独成段

由于 $2 \cdot \min(a_i, a_{i+1}) > \max(a_i, a_{i+1})$，该子段稳定。划分二与划分一不同（长度少 $1$）。因此至少存在两种划分。

必要性：若不存在这样的 $i$，即对所有 $1 \le i < n$，都有：

$$2 \cdot \min(a_i, a_{i+1}) \le \max(a_i, a_{i+1})$$

则任何长度 $\ge 2$ 的连续子段都不稳定（因为取该子段的最小值和最大值一定出现在某对相邻元素中，而该对相邻元素不满足稳定条件）。因此，唯一可行的划分是每个元素单独成段，划分方式唯一。

---

算法步骤

1. 读入测试用例个数 $t$
2. 对于每个测试用例：
   • 读入 $n$ 和数组 $a[1..n]$
   • 遍历 $i = 1$ 到 $n-1$：
     • 如果 $2 \cdot \min(a_i, a_{i+1}) > \max(a_i, a_{i+1})$，则标记为存在
   • 如果存在，输出 "YES"，否则输出 "NO"

---

时间复杂度

• 每个测试用例 $O(n)$
• 总时间复杂度 $O(\sum n)$

---

完整题解代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        bool ok = false;
        for (int i = 0; i < n - 1; i++) {
            if (2 * min(a[i], a[i + 1]) > max(a[i], a[i + 1])) {
                ok = true;
                break;
            }
        }
        
        cout << (ok ? "YES" : "NO") << "\n";
    }
    
    return 0;
}

---

验证样例

输入	相邻对检查	结果
$[2,3,5,7]$	$(2,3): 2\times2=4>3$ ✅	YES
$[115,9,2,28]$	无满足条件	NO
$[8,4,1,6,2]$
$[1,5,4,1,4,7]$	$(5,4): 2\times4=8>5$ ✅	YES
$[100000,100000]$	$2\times100000>100000$ ✅

与题目样例输出完全一致。

---

总结

关键点	结论
稳定性条件	$2 \cdot \min(S) > \max(S)$
至少两种划分的条件	存在相邻元素对满足上述条件
时间复杂度	$O(n)$
空间复杂度	$O(1)$