題目鏈接：點擊查看

題目大意：一個人需要從A點走到B點(在數軸上)，每一次他只有六種走法：

向左走a步

向右走a步

向左走b步

向右走b步

向左走a+b步

向右走a+b步

問最少走多少步

題目分析：我們可以完全轉化成走a步和走b步的形式，從而構造方程：a*x+b*y=abs(A-B)，x即走了多少步a，y即走了多少步b

這樣用拓展歐幾里得就能解出x和y，剩下的就是找最優解的問題了，在這之前，我們先求出通解為

x=x0+k*b/gcd(a,b)

y=y0+k*a/gcd(a,b)

需要分類討論一下：

若x和y同號，那么答案就是max(x,y)，因為我們可以將min(x,y)步都轉化為每次走a+b步，剩下的單獨走a步或單獨走b步

若x和y異號，那么答案就是abs(x)+abs(y)，答案就是先向一個方向走a步或b步，然后再向另一個方向走另一種步數

我們現在假設當x==y時，有x0+k*b/gcd(a,b)=y0+k*a/gcd(a,b)，化簡一下得到k=(y0-x0)/(a/gcd(a,b)+b/gcd(a,b))，因為x和y不一定真的相等，所以我們在[k-1,k+1]的閉區間中更新一下答案防止誤差，最后輸出答案即可

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;LL ex_gcd(LL a,LL b,LL &x,LL &y) {if(b==0){x=1;y=0;return a;}LL ans=ex_gcd(b,a%b,y,x);y-=a/b*x;return ans; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){LL A,B,a,b;scanf("%lld%lld%lld%lld",&A,&B,&a,&b);LL x,y;LL d=ex_gcd(a,b,x,y);LL c=abs(A-B);if(c%d!=0){printf("-1\n");continue;}x*=c/d;y*=c/d;a/=d;b/=d;LL k=(y-x)/(a+b);LL ans=1e18+100;for(int i=k-1;i<=k+1;i++){if((x+b*i)*(y-a*i)>0)ans=min(ans,max(abs(x+b*i),abs(y-a*i)));elseans=min(ans,abs(x+b*i)+abs(y-a*i));}printf("%lld\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的ZOJ - 3593 One Person Game(扩展欧几里得)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。