POJ 2142 The Balance（扩展欧几里得， 函数单调）

扩展欧几里得
题目意思：
给出重量为a和b的砝码，数量无限。要求用天平称出 重量c。 a, b, c都是整数， a != b.
也就是求方程 a * x + b * y = c 的整数解。要求 |x| + |y| 值最小。如果 |x| + |y| 值相同，那么 |a * x| + |b * y| 值最小。
本题要点：
1、扩展欧几里得：
求出 x0 和 y0 是方程 a * x + b * y = c一组解, 那么方程的通解是 x = x0 + b1 * k, y = y0 - a1 * k,
其中，a1 = a / gcd(a, b), b1 = b / gcd(a, b).
2、首先保证 a > b (如果 a < b, swap(a, b), 但后面输出的时候，要 swap 回来)。
要求 |x| + |y| 值最小的话，x只能是正数。通过反证法可以证明。

3、 由 |x| + |y| = |x0 + b1 * k| + |y0 - a1 * k| = x0 + b1 * k + |y0 - a1 * k|
x0 + b1 * k 是随着 k递增的， |y0 - a1 * k| 是先减少，再增加的。因为 a > b, a1 > b1,
|y0 - a1 * k|的减少趋势要比 x0 + b1 * k 的增长趋势要大，因此，当 |y0 - a1 * k| 等于0 的时候，|x| + |y| 取得最小值。
综上所述，找到k，使得|y0 - a1 * k| 等于0， 在k附近枚举几个值，取 |x| + |y| 最小值即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int a, b, c;int exgcd(int a, int b, int &x, int &y)
{
    if(0 == b){
    x = 1, y = 0;return a;}int d = exgcd(b, a % b, x, y);int z = x; x = y; y = z - y * (a / b);return d;
}int main()
{
    int x0, y0, d, a1, b1, x, y;while(scanf("%d%d%d", &a, &b, &c) != EOF){
    if(0 == a && 0 == b && 0 == c)break;bool flag = false;if(a < b)	{
    flag = true;swap(a, b);}d = exgcd(a, b, x0, y0);if(c % d)continue;a1 = a / d, b1 = b / d, x0 *= c / d, y0 *= c / d;// x = x0 + b1 * k, y = y0 - a1 * kint k = y0 / a1;int min_abs = 0x3f3f3f3f;for(int t = k - 2; t <= k + 2; ++t){
    if(min_abs > abs(x0 + b1 * t) + abs(y0 - a1 * t)){
    min_abs = abs(x0 + b1 * t) + abs(y0 - a1 * t);x = x0 + b1 * t, y = y0 - a1 * t;}}if(flag){
    swap(x, y);}printf("%d %d\n", abs(x), abs(y));}return 0;
}/* 700 300 200 500 200 300 500 200 500 275 110 330 275 110 385 648 375 4002 3 1 10000 0 0 0 *//* 1 3 1 1 1 0 0 3 1 1 49 74 3333 1 */