【bzoj2145】【跳跳棋】【二分+lca】

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。  写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

第一行包含三个整数，表示当前棋子的位置a b c。（互不相同）第二行包含三个整数，表示目标位置x y z。（互不相同）

如果无解，输出一行NO。如果可以到达，第一行输出YES，第二行输出最少步数。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct use{int p[5];}pt,at;
int pre[5],aim[5],pd,ad,d,l,r;
bool check(use a,use b){for (int i=1;i<=3;i++) if (a.p[i]!=b.p[i]) return false;return true; 
}
use up(int a[5],int s){use x;int d1=a[2]-a[1],d2=a[3]-a[2];for(int i=1;i<=3;i++)x.p[i]=a[i];if(d1==d2)return x;if(d1<d2){int k=min(s,(d2-1)/d1);s-=k;d+=k;x.p[2]+=k*d1;x.p[1]+=k*d1;}else{int k=min(s,(d1-1)/d2);s-=k;d+=k;x.p[2]-=k*d2;x.p[3]-=k*d2;}if(s)return up(x.p,s);else return x;
}
int main(){for (int i=1;i<=3;i++) scanf("%d",&pre[i]);sort(pre+1,pre+4);for (int i=1;i<=3;i++) scanf("%d",&aim[i]);sort(aim+1,aim+4);pt=up(pre,1000000000);pd=d;d=0;at=up(aim,1000000000);ad=d;d=0;if (!check(pt,at)) {printf("NO\n");return 0;}if (pd>ad){swap(pd,ad);for (int i=1;i<=3;i++) swap(pre[i],aim[i]);}at=up(aim,ad-pd);for (int i=1;i<=3;i++) aim[i]=at.p[i];l=0;r=pd;while (l<=r){int mid=(l+r)>>1;if (!check(up(pre,mid),up(aim,mid))) l=mid+1;else r=mid-1;}printf("YES\n%d",ad-pd+l*2);
}