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

2022年CSP-X复赛真题及题解T2移动棋子题目描述一维的棋盘上有无限多个格子每个格子都有一个编号最中间的格子编号为0 000 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输入 110 20输出 110输入输出样例 2输入 210 -10输出 21输入输出样例 3输入 3-10 -20输出 312说明/提示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∣≤109x , 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。将当前格子编号取相反数从 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。因此最少操作次数为上述三种可行方案的最小值不可行的方案视为无穷大。代码实现#includebits/stdc.husingnamespacestd;intmain(){longlongx,y;//坐标范围可达1e9使用64位整数cinxy;longlongc0(yx)?(y-x):1e18;//0次取反仅在y≥x时有效否则设为无穷大longlongc1llabs(xy)1;//1次取反总成立longlongc2llabs(x-y)2;//2次取反总成立longlongansmin({c0,c1,c2});//取最小值coutans;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}