#3333. 「BalticOI 2020」混合物 题解

问题分析

我们需要判断能否用给定的调味瓶混合出目标比例 $(S_f : P_f : G_f)$，并求出所需的最少瓶数。

关键观察

1. 比例等价性：目标 $(S_f, P_f, G_f)$ 与 $(\alpha S_f, \alpha P_f, \alpha G_f)$ 对于任意 $\alpha > 0$ 是等价的
2. 线性组合：混合调味瓶相当于做线性组合
3. 降维处理：三维比例可以降到二维

数学建模

1. 比例归一化

将目标向量和每个调味瓶向量投影到二维空间：

令目标向量为 $\mathbf{v}_f = (S_f, P_f, G_f)$

对于每个调味瓶 $\mathbf{v}_i = (S_i, P_i, G_i)$，我们考虑其在目标向量正交补空间上的投影。

2. 核心思路

定义新的坐标系：

• 将目标向量 $\mathbf{v}_f$ 作为一个坐标轴
• 找到两个与 $\mathbf{v}_f$ 线性无关的向量作为另外两个坐标轴

实际上，我们可以将问题转化为：寻找非负系数 $c_i$（不全为0），使得：

$$\sum c_i \mathbf{v}_i = \alpha \mathbf{v}_f \quad (\alpha > 0) $$

这等价于：

$$\sum c_i \left(\mathbf{v}_i - \beta_i \mathbf{v}_f\right) = 0 $$

其中 $\beta_i$ 是某个标量。

3. 具体变换方法

令目标向量为 $(s_f, p_f, g_f)$，调味瓶向量为 $(s_i, p_i, g_i)$。

我们想要判断是否存在非负系数 $\lambda_i$（不全为0）使得：

$$\frac{\sum \lambda_i s_i}{\sum \lambda_i p_i} = \frac{s_f}{p_f} \quad \text{且} \quad \frac{\sum \lambda_i p_i}{\sum \lambda_i g_i} = \frac{p_f}{g_f} $$

这可以通过叉积来检验。定义函数：

$$f(\mathbf{v}) = \mathbf{v} \times \mathbf{v}_f = (p \cdot g_f - g \cdot p_f, g \cdot s_f - s \cdot g_f, s \cdot p_f - p \cdot s_f) $$

如果 $\sum \lambda_i f(\mathbf{v}_i) = 0$，且 $\sum \lambda_i \mathbf{v}_i$ 与 $\mathbf{v}_f$ 同向，则达到目标比例。

4. 二维表示

实际上，我们可以将三维向量投影到二维：

令：

$$x_i = \frac{s_i}{s_f} - \frac{g_i}{g_f}, \quad y_i = \frac{p_i}{p_f} - \frac{g_i}{g_f} $$

那么目标是在 $(x,y)$ 平面上找到最少的向量，使得它们的凸包包含原点。

算法设计

1. 凸包方法

将每个调味瓶表示为二维点 $(x_i, y_i)$，问题转化为：

找到包含原点的最少点的凸包

2. 动态维护

由于调味瓶会动态添加和删除，我们需要动态维护这些点，并快速回答包含原点的最小凸包大小。

3. 极角排序

将所有点按极角排序，维护两个指针扫描，找到包含原点的最小点集。

复杂度分析

• 每次查询：$O(k^2)$ 或 $O(k \log k)$，其中 $k$ 是当前调味瓶数量
• 对于 $N \leq 10^5$，需要优化