本文主要是介绍POJ2142 The Balance【二元一次方程】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://poj.org/problem?id=2142
题目大意：
有一个天平，还有质量为a和质量为b的砝码，砝码的数量不限且天平左右两端均可放砝码，现在要求
在天平上惩处质量为c的物品。那么问题来了：怎样放置砝码，才能使放置的砝码数量尽可能的少；当
砝码数量相同时，总质量尽可能的少。
思路：
假设放置x个质量为a的砝码和y个质量为b的砝码，题目就变为了求解a*x + b*y = c的其中一组解，使
得|x| + |y|尽可能小，若相等，则a|x| + b|y|尽可能小。设d = gcd(a，b)，首先用扩展欧几里得算法出
a/d*x + b/d*y = c/d的一组一组解(x0，y0)，那么通解就可以表示为x = x0 + b/d *t，y = y0 - a/d *t。
|x| + |y| = |x0 + b/d*t| + |y0 - a/d*t|。这是一个分段函数，|x0 + b/d*t|单调递增，|y0 - a/d*t|先单
调递减再单调递增。设a > b，则斜率 a/d > b/d，那么 |x| + |y| = |x0 + b/d*t| + |y0 - a/d*t| 总的函
数在 t < y0*d/a 的时候单调递减，在 t >= y0*d/a的时候单调递增。那么|x| + |y|在 t = y0*d/a取得最
小值因为x、y都为整数，t也是整数，所以最小值就在t的上下范围内取整，然后比较两者大小即可得到
结果。
还有一种方法，虽然照做了。。。但是还是不理解。希望大神帮忙解答。
设d = gcd(a，b)，首先用扩展欧几里得算法出a/d*x + b/d*y = c/d的一组一组解(x0，y0)，得到根据
方程来看，因为a、b都为正整数，则如果x为正数，则y为0或负数，若果x为0为负数，则y为正数。先求
出 |x| 的最小值x1为 (x0%b + b) % b，得出|y|的值y1 = |(c/d - a/d*x0)/(b/d)|。同理，也可求出 |y|的最
小值y2为 (y0%a + a) % a，再得出|x|的值x2 = |(c/d - b/d*y0)/(a/d)|。比较x1+y1和x2+y2的值，较小
的就是|x| + |y|最小结果。不清楚为什么这样可以AC。参考博文：http://blog.csdn.net/wmn_wmn/article/details/7800547
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define LL __int64
using namespace std;LL GCD(LL a,LL b)
{if(b == 0)return a;return GCD(b,a%b);
}void ExGCD(LL a,LL b,LL &d,LL &x,LL &y)
{if(!b){x = 1;y = 0;d = a;}else{ExGCD(b,a%b,d,y,x);y -= x*(a/b);}
}int main()
{LL a,b,c,temp,d;while(cin >> a >> b >> c && (a||b||c)){LL x0,y0;LL gcd = GCD(a,b);a /= gcd;b /= gcd;c /= gcd;ExGCD(a,b,d,x0,y0);LL x,y,x1,y1,x2,y2;x1 = x0*c;x1 = (x1%b + b)%b;y1 = (c - a*x1)/b;if(y1 < 0)y1 = -y1;y2 = y0*c;y2 = (y2%a + a)%a;x2 = (c - b*y2)/a;if(x2 < 0)x2 = -x2;if(x1+y1 < x2+y2)x = x1,y = y1;elsex = x2,y = y2;cout << x << ' ' << y << endl;}return 0;
}
这篇关于POJ2142 The Balance【二元一次方程】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
