寻找最优算法：求解飞盘在桶内的卡滞高度问题

问题描述 #

当飞盘投入空桶时，会卡在桶内径小于飞盘外径的位置。桶沿y轴对称，桶壁由连接原点(0,0)与给定坐标点的线段依次连接而成，每次投飞盘时桶均为空。需根据桶壁参数与飞盘半径，计算每个飞盘的卡滞位置（飞盘中心的y坐标）。

输入输出要求 #

输入 #

• 桶壁坐标点：(x₁,y₁),…,(xₘ,yₘ)，满足y₁<y₂<…<yₘ，所有数值为正
• 飞盘半径：r₁,…,rₙ，所有数值为正，且m≤n

输出 #

按升序排列的卡滞高度h₁,…,hₙ

高效算法实现思路 #

1. 预处理桶壁轮廓 #

桶沿y轴对称，任意高度y处的桶内径为2*x(y)，其中x(y)是桶壁在该高度的x坐标。我们先将桶壁补充原点(0,0)作为起始点，得到完整的线段序列：

• 对每个线段区间[y_i, y_{i+1}]（i从0到m-1，y₀=0，x₀=0），推导该区间内x(y)的线性表达式：

  x(y) = x_i + (x_{i+1} - x_i)/(y_{i+1} - y_i) * (y - y_i)
  

• 同时记录每个线段对应的半径范围：
  • 若线段上x(y)随y增大而递增，半径范围为[x_i, x_{i+1}]，此时卡滞高度h随半径r增大而线性递增
  • 若线段上x(y)随y增大而递减，半径范围为[x_{i+1}, x_i]，此时卡滞高度h随半径r增大而线性递减

2. 边界情况处理 #

• 若飞盘半径r小于等于所有x_i中的最小值：飞盘可直接落到桶底，卡滞高度h=0
• 若飞盘半径r大于等于所有x_i中的最大值：飞盘无法进入桶内，卡滞高度为桶口高度yₘ

3. 批量处理飞盘半径 #

为了高效计算所有飞盘的卡滞高度，采用以下步骤：

1. 将输入的飞盘半径数组按升序排序，得到s_r
2. 将预处理得到的半径区间按r的从小到大排序，形成可二分查找的区间列表
3. 对排序后的每个半径s_r[k]，用二分查找快速定位其对应的线段区间，代入该区间的线性公式计算h
4. 最终得到的h数组天然是升序排列，直接输出即可

4. 复杂度分析 #

• 桶壁预处理：O(m)
• 飞盘半径排序：O(n log n)
• 每个半径的区间查找与计算：O(log m)，总查询时间O(n log m)
• 整体复杂度：O(n log n)（因m≤n，O(n log m)可被O(n log n)覆盖），满足高效性要求

内容的提问来源于stack exchange，提问作者user1