2022年CSP-X复赛真题及题解（T2：移动棋子）

2022年CSP-X复赛真题及题解（T2：移动棋子）

题目描述

一维的棋盘上有无限多个格子，每个格子都有一个编号，最中间的格子编号为0 00，0 00号格子向右依次编号为1 , 2 , 3 , ⋯ 1,2,3,\cdots1,2,3,⋯，向左依次编号为− 1 , − 2 , − 3 , ⋯ -1,-2,-3,\cdots−1,−2,−3,⋯。

小明的目标是要将一枚棋子从x xx号格子移动到y yy号格子。

每一次操作有两种选择：

• 操作1 11：向右移动1 11个格子。
• 操作2 22：从当前棋子所在的a aa号格子，直接跳到− a -a−a号格子（如：可以从6 66直接跳到− 6 −6−6，也可以从− 6 −6−6直接跳到6 66）。

可以证明，无论整数x xx和y yy的值是多少，目标总是可以实现的。

请你设计程序，帮小明计算把棋子从x xx号格子移动到y yy号格子需要的最少操作次数。

输入格式

一行，两个整数x xx和y yy，表示要将棋子从x xx号格子移动到y yy号格子。

输出格式

一个整数，表示小明把棋子从x xx号格子移动到y yy号格子需要的最少操作次数。

输入输出样例 1

输入 1

10 20

输出 1

10

输入输出样例 2

输入 2

10 -10

输出 2

1

输入输出样例 3

输入 3

-10 -20

输出 3

12

说明/提示

• 30 % 30\%30%的数据：$ |x|,|y| \le 100$。
• 100 % 100\%100%的数据：x , y x,yx,y都为整数；∣ x ∣ , ∣ y ∣ ≤ 10 9 |x|,|y| \le 10^9∣x∣,∣y∣≤109，x , y x,yx,y不相等。
• 有40 % 40\%40%的数据，∣ x ∣ > ∣ y ∣ |x|>|y|∣x∣>∣y∣。
• 有40 % 40\%40%的数据，∣ x ∣ < ∣ y ∣ |x|<|y|∣x∣<∣y∣。
• 有20 % 20\%20%的数据，∣ x ∣ = ∣ y ∣ |x|=|y|∣x∣=∣y∣。

思路分析

题目允许两种操作：

1. 将当前格子编号加 1（向右移动一格），代价为 1。
2. 将当前格子编号取相反数（从 a 跳到 -a），代价为 1。

目标是从 x 移动到 y，求最少操作次数。

通过分析操作序列的数学结构，可以证明最优解只可能包含 0 次、1 次或 2 次取反操作：

• 0 次取反：全程只使用操作 1。此时必须保证 y ≥ x，操作次数为y - x；否则不可行。
• 1 次取反：先向右走若干步（代价 m₀），取反（代价 1），再向右走若干步（代价 m₁）。最终可到达任意 y，最优步数为|x + y| + 1。
• 2 次取反：先向右走，取反，再向右走，再取反，再向右走。最优步数为|x - y| + 2。

因此，最少操作次数为上述三种可行方案的最小值（不可行的方案视为无穷大）。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){longlongx,y;//坐标范围可达1e9，使用64位整数cin>>x>>y;longlongc0=(y>=x)?(y-x):1e18;//0次取反，仅在y≥x时有效，否则设为无穷大longlongc1=llabs(x+y)+1;//1次取反，总成立longlongc2=llabs(x-y)+2;//2次取反，总成立longlongans=min({c0,c1,c2});//取最小值cout<<ans;return0;}

功能分析

• 功能：计算将棋子从 x 移动到 y 所需的最少操作次数。
• 输入：两个整数 x, y（|x|,|y| ≤ 10⁹，x ≠ y）。
• 输出：一个整数，表示最少步数。
• 时间复杂度：O(1)。
• 空间复杂度：O(1)。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}