自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:17:04，当前版本为作者最后更新于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$）。
   分析这样做的操作步数：

   • $- (x+t) + u = y \quad \Longrightarrow \quad u = y + x + t$。
   • 总步数为：$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);
}