只需小學 \(2\) 年級的水平就可以看懂。

引入

給定一個序列 \(a_1 \sim a_n(1 \le a_i \le 10^9)\)，查詢能否選 \(3\) 個不同的數，使得這三個數的值能組成三角形。

結論：若 \(n \ge 45\)，必有解。

證明：設三個數為 \(A \le B \le C\)，若它們不能組成三角形，有 \(C \ge A + B\)。

那么將數組 \(a\) 排序后，若無解，則有 \(a_i \ge a_{i - 1} + a_{i - 2}(i \ge 3)\)，那么 \(a_i \ge f_i\)，\(f\) 為斐波那契數列。

因為 \(a_i \le 10^9, f_{45} = 11,3490,3170(f_1 = f_2 = 1)\)，所以 \(n \ge 45\) 必有解。

總之，若 \(n \ge p\)，\(f_p > V\)，則必有解。

進階

若要選出 \(3(k + 1)\) 個不同的數，組成 \(k + 1\) 個三角形呢？

結論： \(n \ge p + 3k\) 必有解。

證明：考慮歸納

對于 \(k = 0\)，成立。

若對于 \(k = x\) 成立，下面證明 \(k = x + 1\) 成立

\(n \ge p + 3(k + 1) > p + 3\)，可知一定可以找到一個三個數湊出一個三角形，去掉這三個數，剩余至少有 \(p + 3k\)，有歸納假設可以湊出 \(k\) 個三角形，共 \(k + 1\) 個。

所以對于 \(n\) 較大時，直接輸出 Yes 跑路即可。否則解暴力吧。

但是暴力也是又講究的。將 \(a\) 排序后，不難發現三個數靠的越緊，越容易組成三角形。

所以組成三角形的三個數肯定挨在一起。除非很多個三角形混在一起，如 \([{\color{red}{3}} \ 4 \ {\color{red}{8 \ 8}} \ 9 \ 12 ]\)。