B4097 [CSP-X2022 山东] 移动棋子

chen_zhe · 2025-03-05 12:17:16 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

我们考虑最多使用 2 次翻转（操作 2）就足够求最少步数。具体地，我们讨论三种情况：

1. 不使用翻转
   如果 x \le y，我们可以直接用操作 1 不断加 1 走到 y。所需步数就是 y - x。

2. 使用一次翻转
   思路是先做若干次操作 1，使得当前位置变为 x + t（其中 t 为所做的加 1 次数），然后使用操作 2 将位置变成 -(x+t)；接着再利用操作 1 从 - (x+t) 走到 y（假设这里用了 u 次操作 1。注意加 1 操作只能使数字增大，因此要求 - (x+t) \le y）。
   分析这样做的操作步数：

   • 总步数为：t + 1 + (y + x + t) = 1 + x + y + 2t。
   • 由于 u\geq 0，因此需要选择最小的 t 满足 x+t \ge -y。即当 x+t 不足够大时，需要继续加 1 后再翻转。
   • 最佳选择是令 t = \max(0,-y - x)，此时总操作步数为 1 + x + y + 2\max(0,-y - x)。

3. 使用两次翻转
   当 x > y 时（比如正数向较小正数走，或两负数中较大者向较小者走），直接加 1 无法到达目标，此时可以先翻转，再加 1 ，最后再翻转。 具体过程：

   • 第一步：直接用操作 2 将 x 翻转为 -x（1 步）；
   • 接下来用操作 1 从 -x 加到某个数，然后再翻转回来，使得最终正好到达 y。
   • 分析可得，这样做的最少操作步数为 (x - y) + 2。

最后，我们根据 x,y 的具体满足情况，取以上候选方案的最小值。

参考代码（关键部分）：

// 方案 1：使用 0 次翻转
if(x <= y){
    cand0 = y - x; // 直接加 1 即可到达
    ans = cand0;
}   
// 方案 2：使用 1 次翻转
// 先做 t 次加 1, t 最小满足 x+t >= -y
long long t = 0;
if(x < -y) {
    t = -y - x;
}
cand1 = 1 + x + y + 2*t; // 总步数：t 次加 1, 1 次翻转, 再 (y+x+t) 次加 1
ans = min(ans, cand1);    
// 方案3：使用 2 次翻转（适用于 x > y 的情况）
if(x > y) {
    cand2 = (x - y) + 2;
    ans = min(ans, cand2);
}