「POI2011 R3」木棍 Sticks 题解

题目简述

给定 $k$ 种颜色的木棍，每种颜色有若干根，每根有长度。要求找到三根颜色互不相同的木棍，能组成一个非退化三角形（即满足三角形不等式）。

核心思想

三角形条件 对于三根木棍 $a < b < c$，能构成三角形的条件是：$a + b > c$。

关键观察

要找到三根不同颜色的木棍构成三角形，一个自然的想法是：

考虑长度相近的木棍

维护一个"候选集合"，包含最近看到的几根不同颜色的木棍

检查集合中能否构成三角形

最优策略：贪心 假设我们已经按长度从小到大排序所有木棍（同时记录颜色）。 对于每根木棍，我们只需要检查它和前面最近的两根不同颜色的木棍能否构成三角形。

为什么这样对？

要满足 $a + b > c$，且 $a \leq b \leq c$

对于固定的 $c$，我们希望 $a$ 和 $b$ 尽可能大

但 $a$ 和 $b$ 必须与 $c$ 颜色不同

所以维护两个最近的不同颜色木棍是最优的