本文主要是介绍POJ 2142 The Balance 扩展欧几里得，求|x|+|y|最小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题解：先做出两个函数的图像，然后求|x|+|y|的最小值。|x|+|y|=|x0+b/d *t |+|y0-a/d *t| 这个关于t的函数的最小值应该在t零点附近（在斜率大的那条折线的零点附近，可以观察出来）。以下三种情况中，函数最小值都应该出现在B点附近。
#include<cstdio>
#include<algorithm>
using std::swap;int Egcd ( int a, int b, int &x, int &y )
{int tmp, ret;if ( b == 0 ){x = 1, y = 0;return a;}ret = Egcd ( b, a%b, x, y );tmp = x, x = y, y = tmp-a/b*y;return ret;
}int main()
{int a, b, d;while ( 1 ){scanf("%d%d%d",&a,&b,&d);if ( a+b+d == 0 ) break;bool change = false;if ( a < b ){swap(a,b);change = true;}int gc, x, y, t;int mmin = 99999999, x0, y0, tx, ty;gc = Egcd( a, b, x, y );t = d*y/a;for ( int i = t - 10; i <= t + 10; i++ ){tx = abs((d*x/gc)+(b/gc)*i);ty = abs((d*y/gc)-(a/gc)*i);if ( tx + ty < mmin ){mmin = tx + ty;x0 = tx, y0 = ty;}}if ( change ) swap(x0,y0);printf("%d %d\n",x0,y0);}return 0;
}
这篇关于POJ 2142 The Balance 扩展欧几里得，求|x|+|y|最小的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
