首页 > 代码库 > POJ 2142

POJ 2142

2024-07-21 02:05:21   223人阅读

这道题的难点在于求|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


联系
我们