POJ-2142-The Balance

链接：

题意：

Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Although she could put four 300mg weights on the medicine side and two 700mg weights on the other (Figure 2), she would not choose this solution because it is less convenient to use more weights.
You are asked to help her by calculating how many weights are required.

思路:

考虑扩展欧几里得，可以得到通解.
(x = x_0 + (b/d)*k)
(y = y_0 - (a/d)*k)
另 a > b 可以得到y的下降率较高，可以令y为较低值，枚举两边求解。解为负数时是与所求的在同一边。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>

using namespace std;
typedef long long LL;
const int INF = 1e9;

int ExGcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = ExGcd(b, a%b, x, y);
    int tmp = x;
    x = y;
    y = tmp-(a/b)*y;
    return d;
}

int main()
{
    int a, b, c;
    while(~scanf("%d%d%d", &a, &b, &c) && c)
    {
        bool sp = false;
        if (a < b)
            sp = true, swap(a, b);
        int x, y;
        int d = ExGcd(a, b, x, y);
        x = x*(c/d);
        y = y*(c/d);
        int t = (y*d)/a;
        int ans = INF;
        int resx, resy;
        for (int i = t-5;i <= t+5;i++)
        {
            int tmpx = x+(i*b)/d;
            int tmpy = y-(i*a)/d;
            if (abs(tmpx)+abs(tmpy) < ans)
            {
                resx = tmpx;
                resy = tmpy;
                ans = abs(resx)+abs(resy);
            }
        }
        if (sp)
            swap(resx, resy);
        printf("%d %d
", abs(resx), abs(resy));
    }

    return 0;
}