学步园

分析转自oo

题意吧：一个家伙有一种天平，这种天平只有两种重量的砝码a和b，现在要称出重量为c的物品，问你至少需要多少a和b，答案需要满足a的数量加上b的数量和最小，并且他们的重量和也要最小。（两个盘都可以放砝码）

分析：
这题我刚刚开始还以为是动规或者搜索，也算是碰了一鼻子的灰吧。
假设a砝码我们用了x个，b砝码我们用了y个。那么天平平衡时，就应该满足ax+by==c。x,y为正时表示放在和c物品的另一边，为负时表示放在c物品的同一边。
于是题意就变成了求|x|+|y|的最小值了。x和y是不定式ax+by==c的解。
刚刚上面已经提到了关于x,y的所以解的同式，即
x=x0+b/d*t
y=y0-a/d*t
你是不是下意识的想要穷举所有解，取|x|+|y|最小的？显然是行不通的，仔细分析：|x|+|y|==|x0+b/d*t|+|y0-a/d*t|，我们规定a>b(如果a<b，我们便交换a b)，从这个式子中，我们可以轻易的发现：|x0+b/d*t|是单调递增的，|y0-a/d*t|是单调递减的，而由于我们规定了a>b，那么减的斜率边要大于增的斜率，于是整个函数减少的要比增加的快，但是由于绝对值的符号的作用，最终函数还是递增的。也就是说，函数是凹的，先减小，再增大。那么什么时候最小呢？很显然是y0-a/d*t==0的时候，于是我们的最小值|x|+|y|也一定是在t=y0*d/a附近了。

Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define eps 1e-7
#define LL long long
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int inf=0x3f3f3f3f;

int ex_gcd(int a,int b,int &x,int &y){
    if(!b) {
        x=1; y=0;
        return a;
    }
    int g=ex_gcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return g;
}

int main()
{
    int a,b,c;
    while(scanf("%d %d %d",&a,&b,&c)==3){
        if(a+b+c==0) break;
        bool flag=false;
        if(a<b) {
            swap(a,b);
            flag=true;
        }
        int x0=0,y0=0;
        int g=ex_gcd(a,b,x0,y0);
        x0*=(c/g); y0*=(c/g);
        a/=g; b/=g;
        int MIN=inf,t=y0/a,x1,y1;
        for(int i=t-1;i<=t+1;i++){
            int x=abs(x0+b*i);
            int y=abs(y0-a*i);
            if(x+y<MIN) {
                MIN=x+y;
                x1=x; y1=y;
            }
        }
        if(flag) swap(x1,y1);
        printf("%d %d\n",x1,y1);
    }
    return 0;
}