題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2053A Tender Carpenter

Problem Statement

題目簡述

給定一個長度為 $n$ 的陣列 $a$ 。
定義一個整數集合 $S$ 是穩定的，當且僅當從 $S$ 中任意選取三個元素 $u, v, w$ （可以重複選取），都能構成一個非退化三角形（即滿足三角不等式）。
題目要求將陣列 $a$ 劃分為若干個連續的非空子段，使得每個子段內的元素構成的集合都是穩定的。

判斷是否存在 至少兩種 不同的劃分方式。

Constraints

約束條件

$2 \le n \le 200$
$1 \le a_i \le 10^5$

思路：貪心

題目要求判斷是否可以將陣列 $a$ 劃分成至少兩種不同的「穩定」子段方案。

觀察一：恆存在一種劃分方案

將每個元素 $a_i$ 單獨作為一個子段，這種劃分方式總是有效的。

原因

對於單一元素 $x$ ，從集合 $\{x\}$ 中選取三個元素只能是 $(x, x, x)$ 。由於 $a_i \ge 1$ ，顯然 $x + x > x$ 成立，故單元素集合必定穩定。

因此，問題轉化為：是否存在第二種有效的劃分方式？這意味著至少需要有一個長度大於 $1$ 的子段是穩定的。

觀察二：穩定集合的子集仍然穩定

若集合 $S$ 是穩定的，則對於任意非空子集 $T \subseteq S$ ， $T$ 也是穩定的。

證明

若存在 $u, v, w \in T$ 使得 $(u, v, w)$ 無法構成三角形，由於 $T \subseteq S$ ，則 $u, v, w \in S$ ，這與 $S$ 穩定矛盾。

根據觀察二，若存在一個長度 $\ge 2$ 的穩定子段，我們總可以將其拆分為更小的子段，直到只剩下一個長度為 $2$ 的穩定子段。因此，問題進一步簡化為：

\text{是否存在相鄰的一對元素 } (a_i, a_{i+1}) \text{，使得集合 } \{a_i, a_{i+1}\} \text{ 是穩定的？}

二元集合的穩定條件

對於集合 $\{x, y\}$ （允許重複選取），我們需要檢驗所有可能的三元組：

組合	條件	結論
$(x, x, x)$	$2x > x$	恆成立
$(y, y, y)$	$2y > y$	恆成立
$(x, x, y)$	$2x > y$	需滿足
$(x, y, y)$	$2y > x$	需滿足

綜合以上條件， $\{x, y\}$ 穩定 $\Longleftrightarrow$ $2\min(x, y) > \max(x, y)$ 。

因此，我們只需遍歷陣列，檢查是否存在相鄰的一對元素 $(a_i, a_{i+1})$ 滿足上述條件。若存在，即可將這兩個元素合併為一個子段，其餘元素單獨劃分，從而得到第二種劃分方案。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，只需要遍歷一次陣列。
空間複雜度： $\mathcal{O}(n)$ ，用於存儲輸入陣列。

Code

from itertools import pairwise

def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    for x, y in pairwise(A):
        if 2 * min(x, y) > max(x, y):
            print("YES")
            break
    else:
        print("NO")

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。