POJ.2142 The Balance (拓展欧几里得)

POJ.2142 The Balance (拓展欧几里得)

题意分析

现有2种质量为a克与b克的砝码，求最少 分别用多少个(同时总质量也最小)砝码，使得能称出c克的物品。

设两种砝码分别有x个与y个，那么有ax+by=c。可用拓展欧几里得求解。

若x与y均为正数，说明在天平的同一侧，否则在不同册。

需要注意的是，求出的x与y仅为一组特解，此时需要求|x| + |y| 的最小值。根据：

可得

显然这是不好求的，但我们不妨设a>b，根据斜率关系，不难作图。

可以看出，最小值在t2附近取得，枚举附近值计算，取最小即可。

代码总览

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

typedef int ll;

void exgcd(ll a, ll b, ll& d, ll& x, ll &y)

{

    if(!b){

        d = a,x = 1,y = 0;

    }else{

        exgcd(b, a % b, d, y, x);

        y -= x * (a / b);

    }

}

void cal(ll a, ll b,ll c)

{

    ll gcd,x,y;

    bool isswap = false;

    if(b>a){

        swap(a,b);

        isswap = true;

    }

    exgcd(a,b,gcd,x,y);

    x = x *(c/gcd);

    y = y *(c/gcd);

    int k1 = b /gcd ;

    int k2 = a /gcd ;

    int t = y * gcd / a;

    int min = fabs(x)+ fabs(y),num1 = fabs(x),num2 = fabs(y);

    for(int i = -10; i<=10;++i){

        int temp = t+i;

        if(min>fabs(x+k1*temp) + fabs(y-k2*temp)){

            min = fabs(x+k1*temp) + fabs(y-k2*temp);

            num1 = fabs(x+k1*temp);

            num2 = fabs(y-k2*temp);

        }

    }

    if(isswap) swap(num1,num2);

    printf("%d %d\n",num1,num2);

}

int main()

{

    //freopen("in.txt","r",stdin);

    ll a,b,c;

    while(scanf("%d %d %d",&a,&b,&c)){

        if(a == 0 && b == 0 && c == 0) break;

        cal(a,b,c);

    }

    return 0;

}