UVA 10090 Marbles：擴展歐幾里得與貪心

問題模型

兩種盒子：容量 n1 價格 c1，容量 n2 價格 c2。恰裝 n 顆珠子，最小化成本。n1*x + n2*y = n，x,y ≥ 0 整數，最小化 c1*x + c2*y。

數學解法

1. 擴展歐幾里得求 n1*x0 + n2*y0 = gcd(n1,n2)。
2. 若 n % gcd != 0 無解。
3. 通解：x = x0*(n/g) + (n2/g)*t, y = y0*(n/g) - (n1/g)*t。
4. x>0, y>0 確定 t 範圍 [t_min, t_max]。
5. 成本函數關於 t 單調，比較 c1/n1 與 c2/n2 決定取邊界值。

代碼

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x=1; y=0; return a; }
    ll d = exgcd(b, a%b, y, x);
    y -= a/b * x; return d;
}
int main() {
    ll n, c1, n1, c2, n2;
    while (~scanf("%lld", &n), n) {
        scanf("%lld%lld%llld%lld", &c1,&n1,&c2,&n2);
        ll x,y; ll d = exgcd(n1,n2,x,y);
        if (n%d) { puts("failed"); continue; }
        ll t1 = ceil(-1.0*n*x/d * g / n2); // 詳見代碼
        ll t2 = floor(1.0*n*y/d * g / n1);
        if (t1 > t2) { puts("failed"); continue; }
        if (c1*n2 < c2*n1) { x = n*x/d + n2/d*t2; y = n*y/d - n1/d*t2; }
        else { x = n*x/d + n2/d*t1; y = n*y/d - n1/d*t1; }
        printf("%lld %lld\n", x, y);
    }
}