POJ 2142 TheBalance 模线性方程求解

题目大意：

就是将两种砝码左右摆放，能够在物品放置在天平上时保持平衡

很容易得到 ax + by = t的模线性方程

按题目要求，希望首先满足 |x| + |y| 最小 , 如果有多种情况，再满足所有砝码质量最小，也就是a|x| + b|y|最小

x = x0 + b/g * k

y = y0 - a/g * k

这里可以通过画一个2维坐标图进行观察 x , y 对于k的直线，我假定 b > a ，初始如果 a>b就交换两者数据，记得最后答案交换回来

因为a，b为砝码重量都大于0

所以x是递增直线，y是递减直线

因为假设b > a了，所以x的上升趋势必然大于y的下降趋势

所以只有在x = 0的左右两个点是满足最小的情况的，用xx[2] , yy[2]记录这两个点，然后进行比较即可

当然不交换a ， b 也可以, 那就得在 a > b 的条件下多保存两组数据，此时是在y = 0 的左右两个点

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 int ex_gcd(int a , int &x , int b , int &y)

 {

     if(b == ){

         x =  , y = ;

         return a;

     }

     int ans = ex_gcd(b , x , a%b , y);

     int t = x;

     x = y , y = t - a/b*y;

     return ans;

 }

 void my_swap(int &a , int &b)

 {

     int t = a;

     a = b , b = t;

 }

 int my_abs(int a)

 {

     return a>=?a:-a;

 }

 int main()

 {

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

     int a , b , w;

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

         int x , y;

         bool flag = false;

         if(b < a){

             my_swap(a , b);

             flag = true;

         }

         int g = ex_gcd(a , x , b , y);

         int k = w/g;

         x = k*x , y = k*y;

         a /= g , b /= g;

         int xx[] , yy[];

         if(x >= ){

             xx[] = x - x/b*b;

             xx[] = xx[] - b;

             yy[] = y + x/b*a;

             yy[] = yy[] + a;

         }else{

             xx[] = x - x/b*b+b;

             xx[] = xx[] - b;

             yy[] = y + x/b*a - a;

             yy[] = yy[] + a;

         }

         int ansx , ansy;

         if(my_abs(xx[]) + my_abs(yy[]) == my_abs(xx[]) + my_abs(yy[])){

             if(my_abs(xx[])*a + my_abs(yy[])*b < my_abs(xx[])*a + my_abs(yy[])*b)

                 ansx = my_abs(xx[]) , ansy = my_abs(yy[]);

             else

                 ansx = my_abs(xx[]) , ansy = my_abs(yy[]);

         }

         else{

             if(my_abs(xx[]) + my_abs(yy[]) < my_abs(xx[]) + my_abs(yy[]))

                 ansx = my_abs(xx[]) , ansy = my_abs(yy[]);

             else

                 ansx = my_abs(xx[]) , ansy = my_abs(yy[]);

         }

         if(flag)

             my_swap(ansx , ansy);

         printf("%d %d\n" , ansx , ansy);

     }

     return ;

 }

巴特西

POJ 2142 TheBalance 模线性方程求解

最新文章

热门文章