P1852 跳跳棋 [LCA思想+二分答案]
前言
一道超級好的模型題，構建模型的思想直接學習（集訓隊的果真都是巨佬啊！！）
題目描述
跳跳棋是在一條數軸上進行的。棋子只能擺在整點上。每個點不能擺超過一個棋子。
我們用跳跳棋來做一個簡單的遊戲：棋盤上有\(3\)顆棋子，分別在\(a,b,c\)這三個位置。我們要通過最少的跳動把他們的位置移動成\(x,y,z\)。（棋子是沒有區別的）
跳動的規則很簡單，任意選一顆棋子，對一顆中軸棋子跳動。跳動後兩顆棋子距離不變。一次只允許跳過\(1\)顆棋子。
寫一個程序，首先判斷是否可以完成任務。如果可以，輸出最少需要的跳動次數。
輸入格式
第一行包含三個整數，表示當前棋子的位置\(a\ b\ c\)。（互不相同）
第二行包含三個整數，表示目標位置\(x\ y\ z\)。（互不相同）
輸出格式
如果無解，輸出一行\(NO\)。
如果可以到達，第一行輸出\(YES\)，第二行輸出最少步數。
輸入輸出樣例
輸入
1 2 3
0 3 5
輸出
YES
2
說明/提示
\(20\%\) 輸入整數的絕對值均不超過\(10\)
\(40\%\) 輸入整數的絕對值均不超過\(10000\)
\(100\%\) 絕對值不超過\(10^9\)
分析
搜標籤\(LCA\)搜到的這個題，挺僥倖的。
分析一下，一個三元組，由於每次只能越過一個棋子跳，所以在有序的狀態下只有三種可能：
\(1\)、從中間向兩邊跳。 \(2\)、從左向中間跳，條件是左邊的距離小於右邊。 \(3\)、從右向中間，條件與上邊相反。
根據這個我們可以看出來一個性質：棋子位置的狀態可以近似看作一個二叉樹，而它的根節點就是左右兩邊距離相等的情況，也就是只能從中間向兩邊跳，那麼這個問題的第一問就很好解決了，因為假如兩個三元組跳到所謂的根的狀態的時候的位置不一樣，那麼肯定從一個不能擴展到另一個，這時候只需要讓兩個三元組表示的坐標一直跳，直到跳不了了，那麼就到了根，判斷一下根是否相同，不相同就是\(NO\)，否則繼續向下找需要跳多少步。
第一個問題解決了，接下來解決第二個：
想一下，如果兩個狀態在同一個二叉樹里，而且我們需要求他們之間跳多少步才能相等。！！！！這不就顯然了嗎，樹上距離當然要用\(LCA\)了。可是這個三元組的狀態是沒法建樹的，所以我們只需要用到求\(LCA\)的思想就行了，即：先把兩個狀態距離根的步數統一（對應到求\(LCA\)里就是把深度調到一樣），然後二分向上跳的步數，最後找到一個兩個狀態都向上跳\(L\)步，那麼總的步數就是之前的高度（步數差）加上二分出來的答案的二倍！！成功切掉。
代碼
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5;
const int Inf = 1e9+10;
int a[maxn],b[maxn];
struct Node{//結構體存狀態
int a[maxn];
};
int ans,jl;
int dep1,dep2;
Node js(int *a,int dep){
int d1 = a[2] - a[1];
int d2 = a[3] - a[2];
Node ans;
for(int i=1;i<=3;++i){//記錄狀態
ans.a[i] = a[i];
}
if(d1 == d2)return ans;//如果不能繼續跳，那麼就是根，直接返回
if(d1 < d2){//左邊距離中間小於右邊，那麼就向右邊跳
int step = min(dep,(d2-1)/d1);//找到這個狀態能跳多少步
dep -= step;//總的步數減去這個狀態走的步數
jl += step;//jl記錄的是一共走了多少步
ans.a[2] += step * d1;//更新位置
ans.a[1] += step * d1;
}
else{//左邊距離中間大於右邊，那麼就向左邊跳，下邊都是一樣的，就是更新位置需要減，也就是向左更新
int step = min(dep,(d1-1)/d2);
dep -= step;
jl += step;
ans.a[2] -= step * d2;
ans.a[3] -= step * d2;
}
if(dep)return js(ans.a,dep);//如果還能跳就繼續跳
else return ans;不能就返回
}
int main(){
for(int i=1;i<4;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<4;++i){
scanf("%d",&b[i]);
}
sort(a+1,a+4);
sort(b+1,b+4);
Node zt1 = js(a,Inf);//找到第一個三元組的根
dep1 = jl;
jl = 0;
Node zt2 = js(b,Inf);//第二個三元組的根
dep2 = jl;
jl = 0;
int flag = 0;
for(int i=1;i<4;++i){
if(zt1.a[i] != zt2.a[i])flag = 1;
}
if(flag){//如果根狀態不一樣，直接輸出NO
puts("NO");
return 0;
}
if(dep1 > dep2){
swap(dep1,dep2);
for(int i=1;i<4;++i){
swap(a[i],b[i]);
}
}
int l = 0, r = dep1;
ans = dep2 - dep1;//記錄深度差
zt1 = js(b,ans);//調整到同一深度
for(int i=1;i<4;++i){//記錄下來狀態
b[i] = zt1.a[i];
}
while(l <= r){//二分答案
int mid = (l+r)>>1;
flag = 0;
zt1 = js(a,mid);
zt2 = js(b,mid);
for(int i=1;i<4;++i){
if(zt1.a[i] != zt2.a[i])flag = 1;
}
if(flag)l = mid+1;
else r = mid-1;
}
puts("YES");
printf("%d\n",ans+2*l);
return 0;
}
