UVA10090 Marbles【扩展的欧几里得】

布满荆棘的人生 2023-07-03 04:57 16阅读 0赞

**Discription**  
I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The  
boxes are of two types:  
T ype 1: each box costs c1 Taka and can hold exactly n1 marbles  
T ype 2: each box costs c2 Taka and can hold exactly n2 marbles  
I want each of the used boxes to be filled to its capacity and also to minimize the total cost of  
buying them. Since I find it difficult for me to figure out how to distribute my marbles among the  
boxes, I seek your help. I want your program to be efficient also.

**Input**  
The input file may contain multiple test cases. Each test case begins with a line containing the integer  
n (1 ≤ n ≤ 2, 000, 000, 000). The second line contains c1 and n1, and the third line contains c2 and n2.  
Here, c1, c2, n1 and n2 are all positive integers having values smaller than 2,000,000,000.  
A test case containing a zero for n in the first line terminates the input.

**Output**  
For each test case in the input print a line containing the minimum cost solution (two nonnegative  
integers m1 and m2, where mi = number of T ypei boxes required) if one exists, print ‘failed’ otherwise.  
If a solution exists, you may assume that it is unique.

**Sample Input**  
43  
1 3  
2 4  
40  
5 9  
5 12  
0

**Sample Output**  
13 1  
failed

**题意**  
有n个弹球，现在要把这些弹球全部装进盒子里，第一种盒子每个盒子c1美元，可以恰好装n1个弹球；第二种盒子每个盒子c2元，可以恰好装n2个弹球。找出一种方法把这n个弹球装进盒子，每个盒子都装满，并且花费最少的钱。

**思路**  
这道题，一看样例就很眼熟，其实和[坐船过河(我贪心做的)][Link 1]是一道题，然后我拿坐船那道题的代码交过来发现过不了，超时了，然后我就重新看了下，发现这是道扩展的欧几里得题。  
参考了题解的分析过程。  
[参考题解][Link 2]  
假设第一种盒子买m1个，第二种盒子买m2个，则`n1*m1 + n2*m2 = n`。  
由扩展欧几里得`ax+by=gcd(a,b)`，如果`n%gcd(a,b)!=0`，则方程无解。特解为：

m2=0时，m1=nx/g；
    m1=0时，m2=ny/g;

所以通解为：

m1=nx/g + bk/g；
    m2=ny/g - ak/g,

因为m1和m2不能是负数，k的取值范围：`-nx/b <= k <= ny/a`  
将通解带入，花费为：  
Money=c1\*(-xn/g+bk/g)+c2\*(yn/g-ak/g) = ((b*c1-a*c2)/g)*k+(c1*x*n+c2*y*n)/g;  
所以：  
当b*c1-a*c2 >= 0，k取最小值时花费最少；  
b*c1-a\*c2 < 0，k取最大值时花费最少.

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    
    ll x,y,n,c1,n1,c2,n2,ans1,ans2;
    
    ll ex_gcd(ll a,ll b,ll &x,ll &y)
    { 
        if(b==0)
        { 
            x=1;
            y=0;
            return a;
        }
        ll r=ex_gcd(b,a%b,x,y);
        ll t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }
    
    int main()
    { 
        while(scanf("%lld",&n)!=EOF)
        { 
            if(n==0)
                break;
            scanf("%lld%lld%lld%lld",&c1,&n1,&c2,&n2);
            ll tmp=ex_gcd(n1,n2,x,y);
            ll down=ceil(1.0*-n*x/n2);
            ll up=floor(1.0*n*y/n1);
            if(down>up||n%tmp!=0)
            { 
                printf("failed\n");
                continue;
            }
            else
            { 
                if (c1*n2<c2*n1)
                { 
                    x=n*x/tmp+n2/tmp*up;
                    y=n*y/tmp-n1/tmp*up;
                }
                else
                { 
                    x=n*x/tmp+n2/tmp*down;
                    y=n*y/tmp-n1/tmp*down;
                }
                printf("%lld %lld\n", x, y);
            }
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_43460224/article/details/104125256
[Link 2]: https://blog.csdn.net/LYHVOYAGE/article/details/37932481

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关扩展欧几里得算法 AcWing 877. 扩展欧几里得算法

扩展欧几里得算法 AcWing 877. 扩展欧几里得算法原题链接 [AcWing 877. 扩展欧几里得算法][AcWing 877.] 算法标签数学

不念不忘少年蓝@/ 2023年09月28日 11:41/ 0 赞/ 167 阅读

相关 UVA10090 Marbles【扩展的欧几里得】

Discription I have some (say, n) marbles (small glass balls) and I am going to buy som

布满荆棘的人生/ 2023年07月03日 04:57/ 0 赞/ 17 阅读

相关扩展欧几里得算法

poj 1061题目，青蛙的约会。一开始想暴力求解的。但是之前提交过，tle... 今天过来查一下，说是扩展欧几里得算法。我了个去。这么复杂的名字，得是有多深奥。查了才知

系统管理员/ 2022年09月29日 05:30/ 0 赞/ 357 阅读

相关欧几里得和扩展欧几里得算法

（一）欧几里得算法又称辗转相除法，是求解两个数的最大公约数的算法，基本定义为：设 a=qb+r，其中a，b，q，r都是整数，则：gcd（a，b）= gcd（b，r）利用

ゞ浴缸里的玫瑰/ 2022年08月21日 03:20/ 0 赞/ 383 阅读

相关 Romantic（扩展欧几里得）

The Sky is Sprite. The Birds is Fly in the Sky. The Wind is Wonderful. Blew Throw

分手后的思念是犯贱/ 2022年06月17日 08:37/ 0 赞/ 326 阅读

相关扩展欧几里得算法

问题描述：求解二元一次方程ax+by=c。问题分析：上述的二元一次方程可以用同余方程来进行描述：ax≡cmod(b) 两个问题可以进行转换，但是都可以用扩展的欧几

心已赠人/ 2022年06月15日 10:00/ 0 赞/ 401 阅读

相关欧几里得推扩展欧几里得

欧几里得求整数a,b的最小公约数gcd(a,b)的算法。即欧几里得算法(俗称最小公倍数算法)。有一个重要的公式如下,这个公式的证明略,百度上有. (1) g

我会带着你远行/ 2022年06月13日 09:22/ 0 赞/ 400 阅读

相关欧几里得+扩展欧几里得（理解）

-------------------- 欧几里得： -------------------- 辗转相除法代码： typedef long long

妖狐艹你老母/ 2022年06月05日 05:39/ 0 赞/ 438 阅读

相关扩展欧几里得

GCD 定义欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。结论与证明对于a,b两个正整数（a>b），gcd(a,b)=gcd(a

以你之姓@/ 2022年03月20日 07:53/ 0 赞/ 405 阅读

相关扩展欧几里得算法

下面直接使用简称exgcd就好。先引入紫书上的一个经典问题，求直线方程ax+by+c=0的所有整数解。我们先来看一个简单的，求ax+by=gcd(a,b)的一组整数解。

今天药忘吃喽~/ 2021年09月29日 21:02/ 0 赞/ 594 阅读