首页 > 代码库 > POJ 2142
POJ 2142
这道题的难点在于求|x|+|y|的为最小的值吧。想了好久才想出来,发现自己的数学能力确实跟不上。
可知。x=x0+b/d*t;y=y0-a/d*t;则为
|x0+b/d*t|+|y0-a/d*t|,仔细想想,可以看成的是两条直线方程y绝对值之和。
那么,必然最小值只能出现在两条直线方程的两个零点之间,则枚举两个零点之间的值赋于t即可解。
#include <iostream>#include <algorithm>#include <cstdio>using namespace std;int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}void exgcd(int a,int b ,int &x,int &y){ if(b==0){ x=1;y=0; return; } exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y;}int main(){ int a,b,c,x0,y0; while(scanf("%d%d%d",&a,&b,&c),a||b||c){ int g=gcd(a,b); a/=g; b/=g; c/=g; exgcd(a,b,x0,y0); x0*=c; y0*=c; int minc=(1<<31)-1,summ=(1<<31)-1; int l=-(x0)/b,r=(y0)/a; if(l>r){ int tmp=l; l=r; r=tmp; } // cout<<"x0="<<x0<<‘ ‘<<"y0="<<y0<<endl; // cout<<"a="<<a<<‘ ‘<<"b="<<b<<endl; // cout<<l<<‘ ‘<<r<<endl; int ansx,ansy; for(int i=l-10;i<=r+10;i++){ if(abs(x0+b*i)+abs(y0-a*i)<minc){ minc=abs(x0+b*i)+abs(y0-a*i); summ=g*a*abs(x0+b*i)+g*b*abs(y0-a*i); ansx=abs(x0+b*i); ansy=abs(y0-a*i); } else if(abs(x0+b*i)+abs(y0-a*i)==minc){ if(g*a*abs(x0+b*i)+g*b*abs(y0-a*i)<summ){ summ=g*a*abs(x0+b*i)+g*b*abs(y0-a*i); ansx=abs(x0+b*i); ansy=abs(y0-a*i); } } } printf("%d %d\n",ansx,ansy); }}
POJ 2142
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。