程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 10090 - Marbles (數論)

UVA 10090 - Marbles (數論)

編輯:C++入門知識

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 
#include 
#include 

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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved