Problem：
洛谷端題目鏈接
loj端題目鏈接
題目大意：
在一條數軸上進行跳跳棋游戲，棋子只能擺在整點上，每個點不能擺超過一個棋子，用跳跳棋完成：棋盤上有3顆棋子，分別在a，b，c這三個位置，我們要通過最少的跳動把他們的位置移動成x，y，z，
跳動的規則：任意選一顆棋子，對一顆中軸棋子跳動，跳動后兩顆棋子距離不變，一次只允許跳過1顆棋子，如果可以完成輸出YES以及所需步數，如果不行輸出NO即可，
對，只允許跳過一顆棋子（因為這個想了好久自閉了）
Solution：
看完題目之后第一反應是不是：woc這什么，跟LCA有什么關系？？這哪來的樹？？
那就對了（%dalao）
分類討論，發現對于每一種合法的狀態（也就是沒有棋子重合）只有三種情況能走
1.中點（y）向左邊跳
2.中點（y）向右邊跳
3.左邊（或者右邊）往中間跳 =>可以證明由于只能跳過一顆棋子，在d1!=d2時只能走一個
這好像有點像二叉樹？（將1.2看做子節點，3看做父親節點）
對于1.2情況，我們可以發現（以下以1為例）：
可以知道，d1>d2時左邊的棋子不能跳了，我們最多走d2/d1步，此時d2小于d1了換個方向走，當d2%d1等于0時走d2/d1-1步就到根了，
所以根據這個，我們可以求出開始狀態與結束狀態的祖先，判斷他們的祖先是否相等 =>因為祖先相同就可以通過相反操作得到
這個操作模擬一下就好了，我們可以用除來加快跳(（一個個跳會超時的）
模擬部分：
1 int d1=y-x; 2 int d2=z-y; 3 if(d1<d2) 4 { 5 int step=d2/d1; 6 if(d2%d1==0) step--; 7 if(step>dis) step=dis; 8 x+=step*d1; 9 y+=step*d1; 10 if(x>y) swap(x,y); 11 dis-=step; 12 } 13 else 14 { 15 int step=d1/d2; 16 if(d1%d2==0) step--; 17 if(step>dis) step=dis; 18 z-=d2*step; 19 y-=d2*step; 20 if(z<y) swap(z,y); 21 dis-=step; 22 }View Code
找到了公共祖先之后就可以二分查找（查找往上跳的步數）
l是0，r是min(結果與公共祖先的距離，起點與公共祖先的距離)
1 int l=0,r=min(dep1,dep2),step=0; 2 while(l<=r) 3 { 4 int mid=l+r>>1; 5 b1=go(st,mid); 6 b2=go(ed,mid); 7 if(pd(b1,b2)) step=mid,r=mid-1; 8 else l=mid+1; 9 }View Code
以上是我認為的核心內容（看不懂就感性理解一下）
#include<iostream> #include<cstdio> using namespace std; struct node{ int x,y,z; }st,ed,b1,b2; int dep1,dep2; inline int read(){ char ch; int sign=1; while((ch=getchar())<'0'||ch>'9') if(ch=='-') sign=-1; int res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return res*sign; } inline void sort(node &x){ if(x.x>x.y) swap(x.x,x.y); if(x.x>x.z) swap(x.x,x.z); if(x.y>x.z) swap(x.y,x.z); } inline int findfather(node &b){ int res=0; sort(b); while(b.x+b.z!=b.y*2){ int d1=b.y-b.x; int d2=b.z-b.y; if(d1<d2){ int step=d2/d1; if(d2%d1==0) step--; b.x+=step*d1; b.y+=step*d1; if(b.x>b.y) swap(b.x,b.y); res+=step; }else{ int step=d1/d2; if(d1%d2==0) step--; b.z-=step*d2; b.y-=step*d2; if(b.y>b.z) swap(b.y,b.z); res+=step; } } return res; } inline bool pd(node x,node y){ if(x.x==y.x&&x.y==y.y&&x.z==y.z) return true; return false; } inline int abs(int x){ return x>=0?x:-x; } inline node go(node b,int dis){ sort(b); while(dis){ int d1=b.y-b.x; int d2=b.z-b.y; if(d1<d2){ int step=d2/d1; if(d2%d1==0) step--; if(step>dis) step=dis; b.x+=step*d1; b.y+=step*d1; if(b.x>b.y) swap(b.x,b.y); dis-=step; }else{ int step=d1/d2; if(d1%d2==0) step--; if(step>dis) step=dis; b.z-=d2*step; b.y-=d2*step; if(b.z<b.y) swap(b.z,b.y); dis-=step; } } return b; } int main(){ st.x=read();st.y=read();st.z=read(); ed.x=read();ed.y=read();ed.z=read(); sort(st);sort(ed); b1=st;b2=ed; dep1=findfather(b1); dep2=findfather(b2); if(!pd(b1,b2)){ printf("NO\n"); return 0; }else{ int c=abs(dep1-dep2); if(dep1<dep2) ed=go(ed,c); else if(dep1>dep2) st=go(st,c); int l=0,r=min(dep1,dep2),step=0; while(l<=r){ int mid=l+r>>1; b1=go(st,mid); b2=go(ed,mid); if(pd(b1,b2)) step=mid,r=mid-1; else l=mid+1; } printf("YES\n"); printf("%d",step*2+c); } return 0; }complete code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/86637.html
標籤：C++