UVA 10090 - Marbles (数论)

本文主要是介绍UVA 10090 - Marbles (数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 10090 - Marbles

题目链接

题意：有两种盒子，一种代价c1，能装n1个珠子，一种代价c2，能装n2个珠子，问如何正好装n个珠子，并且使得代价最少。
思路：利用扩展欧几里得算法求出n1∗x+n2∗y=n的一个解(x′,y′)
就可以知道x,y的通解分别为
x=x′∗n/gcd(n1,n2)+n2/gcd(n1,n2)∗t
y=y′∗n/gac(n1,n2)−n1/gcd(n1,n2)∗t
由于x > 0 && y > 0，就可以求出t的范围。
那么t越小x越小，y越大，反之亦然。
之后利用贪心，看那种盒子比例比较优，就尽量让哪种盒子多即可。
代码：

#include <stdio.h>
#include <string.h>
#include <math.h>long long extend_gcd(long long a, long long b, long long &x, long long &y) {if (b == 0) {x = 1; y = 0; return a;}long long d = extend_gcd(b, a % b, y, x);y -= a / b * x;return d;
}long long n, c1, c2, n1, n2;int main() {while (~scanf("%lld", &n) && n) {scanf("%lld%lld%lld%lld", &c1, &n1, &c2, &n2);long long x, y;long long d = extend_gcd(n1, n2, x, y);long long downk = ceil(1.0 * -n * x / n2);long long upk = floor(1.0 * n * y / n1);if (downk > upk || n % d) {printf("failed\n");continue;}if (c1 * n2 < c2 * n1) {x = n * x / d + n2 / d * upk;y = n * y / d - n1 / d * upk;}else {x = n * x / d + n2 / d * downk;y = n * y / d - n1 / d * downk;}printf("%lld %lld\n", x, y);}return 0;
}

这篇关于UVA 10090 - Marbles (数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---