时间限制: 1000 ms 内存限制: 524288 KB
原题来自：BZOJ 2144
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有三颗棋子，分别在 a,b,c 这三个位置。我们要通过最少的跳动把他们的位置移动成 x,y,z（注意：棋子是没有区别的）。
跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。
写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
第一行包含三个整数，表示当前棋子的位置 a, b, c。第二行包含三个整数，表示目标位置 x, y, z。
如果无解，输出一行 NO。如果可以到达，第一行输出 YES，第二行输出最少步数。
1 2 3
0 3 5YES
2对于 20% 的数据，输入整数的绝对值均不超过 10；
对于 40% 的数据，输入整数的绝对值均不超过 104；
对于 100% 的数据，输入整数的绝对值不超过 10^9109。保证 a,b,c 互不相同，x,y,z 互不相同。
sol：转自zhber的blog
#include <bits/stdc++.h> using namespace std; const int inf=1000000000; struct Record { int a[5]; }Start,End; int Depth=0; inline Record Jump(Record Now,int Step) { Record tmp=Now; int t1=Now.a[2]-Now.a[1],t2=Now.a[3]-Now.a[2]; if(t1==t2) return tmp; if(t1<t2) { int t=min(Step,(t2-1)/t1); Step-=t; Depth+=t; tmp.a[1]+=t*t1; tmp.a[2]+=t*t1; } else { int t=min(Step,(t1-1)/t2); Step-=t; Depth+=t; tmp.a[2]-=t*t2; tmp.a[3]-=t*t2; } return (Step)?(Jump(tmp,Step)):(tmp); } inline bool operator !=(Record p,Record q) { int i; for(i=1;i<=3;i++) if(p.a[i]!=q.a[i]) return 1; return 0; } int main() { int i,D_Start,D_End,ans=0; for(i=1;i<=3;i++) scanf("%d",&Start.a[i]); sort(Start.a+1,Start.a+4); for(i=1;i<=3;i++) scanf("%d",&End.a[i]); sort(End.a+1,End.a+4); Record Last1=Jump(Start,inf); D_Start=Depth; Depth=0; Record Last2=Jump(End,inf); D_End=Depth; Depth=0; if(Last1!=Last2) return 0*puts("NO"); if(D_Start>D_End) {swap(Start,End); swap(D_Start,D_End);} ans=D_End-D_Start; Record pp=Jump(End,ans); End=pp; int l=0,r=D_Start; while(l<=r) { int mid=(l+r)>>1; (Jump(Start,mid)!=Jump(End,mid))?(l=mid+1):(r=mid-1); } puts("YES"); printf("%d\n",ans+2*l); return 0; }
原文：https://www.cnblogs.com/gaojunonly1/p/10353158.html
