「CEOI2024」文本编辑器 题解

题目分析

这是一个光标移动的最优化问题，需要将光标从 $(s_l, s_c)$ 移动到 $(e_l, e_c)$，使用最少的按键次数。光标移动规则如下：

• 左右移动：在同一行内移动，到达行首/行尾时会跳到上一行/下一行的末尾
• 上下移动：保持列数不变，但如果目标行的长度小于当前列数，则跳到目标行末尾

核心思路

关键观察

1. 最优路径结构：最优解通常先通过垂直移动到达某个中间行，然后水平调整列位置，最后再垂直移动到目标行
2. 瓶颈列概念：在连续的行序列中，光标能保持的最小列数受限于这些行中最短的行长度
3. 预处理思想：预先计算从起始行到达每一行的最小代价

算法框架

使用动态规划预处理，然后枚举中间行计算总代价。

代码详解

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, sl, sc, el, ec, len[1000005], ans = 1e18, now;
int op[1000005], ed[1000005];  // op[i]: 到达第i行行首的最小代价，ed[i]: 到达第i行行尾的最小代价

初始化与输入处理

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> sl >> sc >> el >> ec;
    sc--;  // 转换为0-based列索引，方便计算
    ec--;
    now = sc;

    for (int i = 1; i <= n; i++) {
        cin >> len[i];
    }

注释：将列坐标转换为0-based，这样列范围变成 $[0, l_i]$，其中0表示行首，$l_i$ 表示行尾。

特殊情况处理

    now = sc;
    for (int i = sl; i <= el; i++) {
        now = min(now, len[i]);  // 计算从起始行到目标行路径上的最小列限制
    }
    
    if (now == sc) {  // 如果起始列不超过路径上的所有行长度
        ans = abs(sl - el) + abs(sc - ec);  // 可以直接直线移动
    }

注释：如果起始列 $s_c$ 不超过从 $s_l$ 到 $e_l$ 所有行的长度，那么最优解就是垂直移动 $|s_l - e_l|$ 步加上水平移动 $|s_c - e_c|$ 步。

预处理数组初始化

    for (int i = 0; i <= n + 1; i++) {
        op[i] = 1e18;  // 初始化为无穷大
        ed[i] = 1e18;
    }

向上预处理

    now = sc;
    for (int i = sl; i >= 1; i--) {  // 从起始行向上遍历
        now = min(now, len[i]);  // 更新当前能保持的最小列数
        op[i] = min(op[i], now + (sl - i));  // 到达第i行行首的代价
        op[i + 1] = min(op[i + 1], len[i] - now + 1 + (sl - i));  // 到达下一行行首
        ed[i] = (sl - i) + len[i] - now;  // 到达第i行行尾的代价
    }

公式说明：

• $op[i] = now + (sl - i)$：垂直移动 $(sl-i)$ 步，水平移动 $now$ 步到行首
• $op[i+1] = (len[i] - now + 1) + (sl - i)$：先到当前行行尾，再按右键到下一行行首
• $ed[i] = (sl - i) + (len[i] - now)$：垂直移动 $(sl-i)$ 步，从当前列水平移动到行尾

向下预处理

    now = sc;
    for (int i = sl; i <= n; i++) {  // 从起始行向下遍历
        now = min(now, len[i]);  // 更新当前能保持的最小列数
        op[i] = min(op[i], now + (i - sl));  // 到达第i行行首的代价
        op[i + 1] = min(op[i + 1], len[i] - now + 1 + (i - sl));  // 到达下一行行首
        ed[i] = (i - sl) + len[i] - now;  // 到达第i行行尾的代价
    }

代价传播优化

    for (int i = 2; i <= n; i++) {
        op[i] = min(op[i], op[i - 1] + 1);  // 从左向右传播最小代价
    }
    
    for (int i = n - 1; i >= 1; i--) {
        op[i] = min(op[i], op[i + 1] + 1);  // 从右向左传播最小代价
        ed[i] = min(ed[i], op[i + 1] + 1);  // 通过下一行行首更新当前行行尾代价
    }

注释：这部分通过相邻行的关系进一步优化代价，利用了「从相邻行移动过来只需要1步」的性质。

计算最终答案

    now = len[el];  // 初始化当前最小列数为目标行长度
    
    // 从目标行向下寻找中间行
    for (int i = el; i <= n; i++) {
        now = min(now, len[i]);  // 更新最小列数
        ans = min(ans, i - el + min(op[i] + ec, ed[i] + abs(now - ec)));
    }
    
    now = len[el];  // 重新初始化
    
    // 从目标行向上寻找中间行
    for (int i = el; i >= 1; i--) {
        now = min(now, len[i]);  // 更新最小列数
        ans = min(ans, el - i + min(op[i] + ec, ed[i] + abs(now - ec)));
    }

公式解释：

• $i - el$ 或 $el - i$：从中间行到目标行的垂直移动步数
• $op[i] + ec$：先到中间行行首，再水平移动到目标列
• $ed[i] + |now - ec|$：先到中间行行尾，再水平移动到目标列（受限于最小列数 $now$）

输出结果

    cout << ans;
    return 0;
}

时间复杂度

• 预处理：$O(N)$
• 答案计算：$O(N)$
• 总复杂度：$O(N)$，适用于 $N \leq 10^6$ 的数据规模

总结

本题的关键在于将二维光标移动问题转化为对关键位置（行首、行尾）的预处理，然后通过枚举中间行来组合出最优解。算法充分利用了光标移动的特殊性质，避免了直接建图求最短路的昂贵开销。