B. Mahmoud and a Triangle

---

🔺 B. Mahmoud 与三角形

时间限制： 2 秒 内存限制： 256 MB

---

📘 题目描述

Mahmoud 拥有 n 条线段，第 i 条线段的长度为 a_i。

Ehab 向他发起挑战： 👉 要求恰好选出 3 条线段，组成一个非退化三角形。

Mahmoud 是个谨慎的人，只有在 确定能赢 的情况下才会接受挑战。 现在请你帮助他判断： 是否存在 3 条线段，可以组成一个非退化三角形？

---

📐 三角形说明

• Mahmoud 必须恰好使用 3 条线段

• 不允许拼接线段

• 不允许改变线段长度

• 非退化三角形：

  • 面积 大于 0
  • 等价条件：严格满足三角形不等式

---

🎯 任务目标

给定所有线段长度，判断是否 存在某 3 条线段，可以组成一个非退化三角形。

---

📥 输入格式

• 第一行：一个整数 n 表示线段数量

• 第二行：n 个整数

  a1, a2, …, an
  

  表示每条线段的长度

---

📤 输出格式

• 输出一行：

  • "YES" —— 如果可以选出 3 条线段组成非退化三角形
  • "NO" —— 否则

---

📌 数据范围

• 3 ≤ n ≤ 10^5
• 1 ≤ a_i ≤ 10^9

---

🧪 样例一

输入

5
1 5 3 2 4

输出

YES

说明

选择线段长度为 2, 4, 5：

2 + 4 > 5

满足三角形不等式，可以组成非退化三角形。

---

🧪 样例二

输入

3
4 1 2

输出

NO

说明

排序后为 [1, 2, 4]：

1 + 2 = 3 ≤ 4

无法构成非退化三角形。

---

🧠 关键数学结论（教学重点）

三条边 x ≤ y ≤ z 可以构成 非退化三角形 的充要条件是：

x + y > z

---

🧩 解题思路（核心观察）

1. 将所有线段长度排序

2. 只需检查 任意连续的三条线段

3. 若存在：

   a[i] + a[i+1] > a[i+2]
   

   则答案为 "YES"

4. 若所有连续三元组都不满足，则 "NO"

📌 为什么只看连续三个？

• 排序后，连续三条是 最有可能 满足不等式的一组
• 如果它们都不行，更分散的组合只会更差

---

🧠 算法复杂度

• 排序：O(n log n)
• 扫描一次：O(n)
• 满足本题数据规模要求

---

🧭 知识点

• 三角形不等式
• 排序后的性质
• 将“组合问题”转化为“线性扫描”
• 数学 + 贪心的经典结合

---