UVa 10090 - Marbles

#数学 #扩展欧几里德
Published on 2016-03-02

题目地址

描述

有 nn 个弹珠，你需要购买盒子将弹珠全部放进去（不允许有盒子空着）。有两种盒子：

  • 第一种：价格 c1c_1，恰好装 n1n_1 个弹珠。
  • 第二种：价格 c2c_2，恰好装 n2n_2 个弹珠。

你的任务就是求算出一种购买方案，使得把弹珠全部放入盒子的花销最小。如果不存在，输出 failed。

样例输入

43
1 3
2 4
40
5 9
5 12
0

样例输出

13 1
failed

分析

这题还是独立想出来的，不错。
设第一种盒子买 xx 个，第二种盒子买 yy 个；第一种盒子能装 aa 个价格 m1m_1；第二种盒子能装 bb 个，价格 m2m_2，那么有：

ax+by=nax + by = n

当 或 n<min(a,b)n < \min(a, b) 时无解。
用扩展欧几里得算法求出一组满足方程的解 x0,y0x_0, y_0（但不一定满足题意，花费也不一定最小）。
我们知道这个方程有无数组解，扩展出更多解的方法是：

关键在于求取合适的 tt，使得 x,yx, y 既是整数，又花费最小。
设 Δx=bgcd(a,b),Δy=agcd(a,b)\Delta x = \frac{b}{\gcd(a, b)}, \Delta y = \frac{a}{\gcd(a, b)}
算出 tt 的取值范围，求解这个不等式组：

{x0+Δxt≥0y0+Δyt≥0\begin{cases}x_0 + \Delta xt \ge 0\\y_0 + \Delta yt \ge 0\end{cases}

解出来是：

−xΔx≤t≤yΔy-\frac{x}{\Delta x} \le t \le \frac{y}{\Delta y}

如果这个无整数 tt 解，则输出 failed。
我们接着计算出花费关于 tt 的表达式：

f(t)=x0m1+y0m2+t⋅m1b−m2agcd(a,b)f(t) = x_0m_1 + y_0m_2 + t\cdot\frac{m_1b - m_2a}{\gcd(a, b)}

设 m1b−m2agcd(a,b)=delta\frac{m_1b - m_2a}{\gcd(a, b)} = \text{delta} 这是个关于 tt 的一次函数，显然 m1b−m2a>0m_1b - m_2a > 0 时，函数单调递增，取端点 ⌊yΔy⌋\left\lfloor\frac{y}{\Delta y}\right\rfloor。m1b−m2a<0m_1b - m_2a < 0 时，函数单调递减，取端点 ⌈xΔx⌉\left\lceil\frac{x}{\Delta x}\right\rceil。
我之前是直接讨论斜率，没有明确弄出自变量的范围，导致 WA 半天找不出原因，看来运用常规数学处理方法才是简洁的，不易错的。

代码

//  Created by Sengxian on 3/2/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 10090 扩展 Eculid
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

void extgcd(int a, int b, ll &x, ll &y) {
    if(b == 0) {
        x = 1, y = 0;
    }else {
        extgcd(b, a % b, y, x);
        y -= a / b * x;
    }
}

int n, a, b, c, d;
int main() {
    while(n = ReadInt(), n) {
        c = ReadInt(), a = ReadInt(), d = ReadInt(), b = ReadInt();
        int gcd = __gcd(a, b);
        ll x, y;
        if(n % gcd || n < min(a, b)) {puts("failed"); continue;}
        extgcd(a, b, x, y);
        x *= n / gcd, y *= n / gcd;
        ll deltaX = b / gcd, deltaY = a / gcd, delta = c * deltaX - d * deltaY;
        double l = ceil((double)-x / deltaX), r = floor((double)y / deltaY);
        if(l > r) {puts("failed"); continue;}
        if(delta > 0) x += l * deltaX, y -= l * deltaY;
        else x += r * deltaX, y -= r * deltaY;
        printf("%lld %lld\n", x, y);
    }
    return 0;
}

附加输入

1791
2000000000 13
1 21
1791
1 21
10 13
1791
10 21
1 13
1791
1 13
10 21
1791
10 13
1 21
1
10 3
1 2
1
1 2
10 3
0

附加输出

15 76
76 15
11 120
120 11
15 76
failed
failed
UVa 557 - Burger