转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
Checkers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 775 Accepted Submission(s): 228
The chessboard is like the Number Axes now, with each integer point able to hold a checker. At initial status there are three checkers on three different integer points , and through the game there always are three checkers. Every time, they can choose a checker A to jump across a pivot checker B to a new position(but the distance between old A and B equals to new A and B, and there should be no other checkers except B in the range [old A, new A]).
After playing for a while, they wonder whether an given status a,b,c can be transferred to x,y,z. obeying the rules. Since the checkers are considered the same, it is unnecessary for a must jump to x.
The second line is x,y,z.
They are all integers in range (-10^9, 10^9) and the two status are valid.
If it is YES, then output the least steps in the second line.
0 3 5
2
The middle checker jumps to position 0, and the status is 0 1 3
Then , the middle one jumps to 5.
题意：
给出三个点数轴上的起始为止与终止位置，问能否通过不断的跳跃从起始位置到终止位置(ps:不需要一一对应)，每次跳跃时不得跨过两个点，若能，则给出最少需要几次操作
分析：
不妨设a<b<c,x<y<z。
由于一次不能跨越两个点。若b-a>c-b，则只能进行(1)b->2a-b-a或者(2)b->2c-b或者(3)a->2b-a;
若b-a<c-b，则只能进行(1)b->2a-b-a或者(2)b->2c-b或者(3)c->2b-c;
若b-a=c-b，则只能进行(1)b->2a-b-a或者(2)b->2c-b;
我们可以发现，若每次选取(1)(2)操作，则三个数在数轴上的跨度会不断变大，我们可以视为其分别向左儿子和右儿子移动，
若选取(3)操作，则三个数在数轴上的跨度会不断变小，对此，我们可以将其视为向父亲结点移动(因为对于每种状态，其对应的(3)操作是唯一的，这恰好对应这树的父亲结点是唯一的)。
通过一定次数的向父亲结点移动，我们可以发现最终一定会变成第三种状态。也就是对于判断yes还是no，我们只需要判断其所对应的根节点是否相同，若不同，则必定不能从初始状态转移到最终状态。
那么，如何快速地求出某一状态进行若干操作之后的状态呢？
我们假设a<b<c，并且c-b>a-b。那么，一次(3)操作之后会变成b,2b-a,c。也就是相当于给a和b同时加上了b-a。那么对于这样需要移动几次呢？(c-b)/(b-a)？
这是不对的，例如1，2，4。若移动二次，则会变成3,4,4。也就是我们要避免b-a=c-b的发生。即对于(c-b)%(b-a)==0时，我们需要少移一次。
于是，利用向下取整的特性，我们可以发现只要移(c-b-1)/(b-a)次。
如此，不断往复，我们就可以快速地求出移动若干次的状态，然后二分搞一下就行了
//#####################
//Author:fraud
//Blog: http://www.cnblogs.com/fraud/
//#####################
#include <iostream>
#include <sstream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
using namespace std;
#define XINF INT_MAX
#define INF 0x3FFFFFFF
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;
#define MAXN 10
ll a[MAXN],b[MAXN];
ll ra[MAXN],rb[MAXN];
void gcd(ll *x,ll &d){
ll l1=x[]-x[];
ll l2=x[]-x[];
ll t;
while(l1!=l2){
if(l1<l2){
t=(l2-)/l1;
ll tmp=t*l1;
x[]+=tmp;
x[]+=tmp;
}else{
t=(l1-)/l2;
ll tmp=t*l2;
x[]-=tmp;
x[]-=tmp;
}
d+=t;
l1=x[]-x[];
l2=x[]-x[];
//gcd(x,d);
}
}
void gao(ll *x,ll d){
ll l1=x[]-x[];
ll l2=x[]-x[];
ll t;
while(d>){
if(l1<l2){
t=(l2-)/l1;
if(t>d)t=d;
ll tmp=t*l1;
x[]+=tmp;
x[]+=tmp;
}else {
t=(l1-)/l2;
if(t>d)t=d;
ll tmp=t*l2;
x[]-=tmp;
x[]-=tmp;
}
d-=t;
l1=x[]-x[];
l2=x[]-x[];
}
} int main()
{
ios::sync_with_stdio(false);
while(scanf("%I64d%I64d%I64d",&a[],&a[],&a[])!=EOF){
for(int i=;i<;i++)scanf("%I64d",&b[i]);
sort(a,a+);
sort(b,b+);
for(int i=;i<;i++)ra[i]=a[i];
for(int i=;i<;i++)rb[i]=b[i];
ll d1=,d2=;
bool flag=;
for(int i=;i<;i++)if(ra[i]==ra[i+])flag=;
for(int i=;i<;i++)if(rb[i]==rb[i+])flag=;
if(flag){
printf("NO\n");
continue;
}
gcd(ra,d1);
gcd(rb,d2);
flag=;
for(int i=;i<;i++)
if(ra[i]!=rb[i])flag=;
if(flag){
printf("NO\n");
continue;
}
printf("YES\n");
ll ans = ;
ll tmp = ;
if(d1>d2)gao(a,d1-d2);
else gao(b,d2-d1);
ll l=,r=min(d1,d2);
while(l<=r){
ll mid=(l+r)>>;
for(int i=;i<;i++)ra[i]=a[i];
for(int i=;i<;i++)rb[i]=b[i];
gao(ra,mid);
gao(rb,mid);
bool flag=;
for(int i=;i<;i++)
if(ra[i]!=rb[i])flag=;
if(!flag){
tmp=mid;
r=mid-;
}else {
l=mid+;
}
}
printf("%I64d\n",tmp*+max(d1-d2,d2-d1));
}
return ;
}