「KTSC 2022 R1」飞天松鼠 题解

问题分析

我们需要找到飞天松鼠从起点 $(0,L)$ 到终点 $(D_N,R)$ 的最小花费路径，要求：

• 必须依次经过所有柱子
• 飞行时高度下降距离等于水平移动距离
• 不能在空中碰到地面
• 在柱子上爬升需要花费，下滑免费

核心思路

关键观察

1. 飞行约束：从柱子 $i$ 飞到柱子 $j$ 需要满足 $h_i \geq d_j - d_i$
2. 贪心策略：在费用较低的柱子上尽量多爬升
3. 可达性预处理：从右向左传递高度限制

算法框架

1. 可行性检查：验证是否存在可行路径
2. 高度传递：从终点向起点传递可达高度
3. 贪心选择：在费用最小的柱子上进行爬升

代码详解

数据结构

struct seg {
    ll st[mxn*4];  // 线段树维护最小费用
    
    void init(int n, int s, int e, ll* v) {
        if(s == e) {
            st[n] = v[s];
            return;
        }
        int m = s + (e-s)/2;
        init(n*2, s, m, v);
        init(n*2+1, m+1, e, v);
        st[n] = min(st[n*2], st[n*2+1]);  // 维护区间最小值
    }
    
    void del(int n, int s, int e, int x) {
        // 删除位置x的值（设为无穷大）
        if(s == e) {
            st[n] = inf;
            return;
        }
        // ... 递归删除
    }
    
    int qry(int n, int s, int e, ll x) {
        // 查询第一个值 ≤ x 的位置
        if(st[n] > x) return e+1;
        if(s == e) return s;
        // ... 递归查询
    }
} st;

主要算法步骤

1. 输入处理和初始化

int n = D.size();
for(int i=0; i++<n;)
    d[i] = D[i-1], h[i] = H[i-1], w[i] = W[i-1];

2. 可行性检查

for(int i=1; i<n; i++)
    if(h[i] < dd[i])  // 如果柱子高度小于到下一柱子的距离
        return -1;    // 无法飞行

3. 高度传递（从右向左）

h[n] = R;
for(int i=n; i-->1;)
    h[i] = min(h[i], h[i+1] + dd[i]);

这一步确保：从每个柱子都能到达后续柱子，避免"死路"

4. 线段树初始化

st.init(1, 1, n, w);  // 构建费用线段树

5. 贪心爬升

int i=1, j=1, k=0;
int ch = min(L, h[1]);  // 当前高度
ll ans = 0;

while(i < n) {
    // 计算从i能直接飞到的最大j
    while(j < n && d[j+1]-d[i] <= h[i])
        j++;
    
    // 删除已处理的位置
    while(k < i)
        st.del(1, 1, n, ++k);
    
    // 找到费用最小的可达柱子
    int nx = st.qry(1, 1, n, w[i]);
    
    if(nx > j) {
        // 没有更便宜的柱子，在当前柱子爬升
        ans += w[i] * (h[i] - ch);
        ch = h[i] - dd[i];  // 飞到下一柱子后的高度
        i++;
    } else if(ch < d[nx]-d[i]) {
        // 需要爬升才能飞到更便宜的柱子
        ans += w[i] * (d[nx]-d[i] - ch);
        ch = 0;  // 刚好到达
        i = nx;
    } else {
        // 可以直接飞到更便宜的柱子
        ch -= d[nx]-d[i];  // 高度下降
        i = nx;
    }
}

6. 最终调整

ans += w[n] * (h[n] - ch);  // 在最后一根柱子调整到目标高度
return ans;

算法正确性

贪心选择证明

算法始终选择费用最小的可达柱子作为下一个目标：

• 如果在当前柱子爬升更便宜，就尽量爬升
• 如果能飞到费用更低的柱子，就飞到那里再爬升
• 这保证了总体费用最小化

高度传递的意义

从右向左传递高度限制：

• 确保路径的连通性
• 避免进入无法到达终点的区域
• 为贪心选择提供准确的上界

复杂度分析

时间复杂度

• 高度传递：$O(N)$
• 线段树操作：$O(N \log N)$
  • 初始化：$O(N)$
  • 每次删除和查询：$O(\log N)$
• 主循环：$O(N \log N)$
• 总复杂度：$O(N \log N)$

空间复杂度

• 数组存储：$O(N)$
• 线段树：$O(N)$
• 总空间：$O(N)$

算法优势

$1.$ 高效性：$O(N \log N)$ 处理大规模数据

$2.$ 正确性：严格的数学证明保证最优解

$3.$ 实用性：处理各种约束条件

$4.$ 鲁棒性：完善的错误检测机制

总结

该算法通过巧妙的贪心策略和线段树优化，解决了飞天松鼠的最优路径问题。核心思想是"在费用最低的地方爬升"，通过数据结构快速找到最优决策点，保证了算法的高效性和正确性。