LG7441 「EZEC-7」Erinnerung

发布于 2021-03-24  3.74k 次阅读


题面

分析

显然价值为 $-K$ 的落叶或雪花对我们来说是没有意义的。

下面我们假设 $x > y$。

对于一个价值为 $x \times i$ 的物品,我们令其与 $y \times ( \lfloor \frac K y \rfloor -i+1)$ 匹配。两物品和为

$x \times i + y \times (\lfloor \frac K y \rfloor -i+1)=(x-y)\times i + y \times (\lfloor \frac K y\rfloor +1)$

由于 $y \times (\lfloor \frac K y \rfloor +1) > K$ 且 $(x-y) \times i>0$,所以两物品之和满足题目所给的条件。

显然 $\forall 1 \le i \le \lfloor \frac K x\rfloor,\lfloor \frac K y\rfloor -i +1 \ge 1$,所以答案即为 $\lfloor \frac K x\rfloor$。

代码

需要注意特判,并注意特判的时候不要出现对 $0$ 取模的情况。

/**
 * @author Macesuted
 * @date 2021-03-20
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <bits/stdc++.h>
using namespace std;

using io::getch;
using io::putch;
using io::read;
using io::write;

int main() {
    int T = read<int>();
    while (T--) {
        long long x = read<long long>(), y = read<long long>(), K = read<long long>();
        if (x == 0 && y == 0)
            write(0);
        else if (x == 0)
            write(K % y == 0);
        else if (y == 0)
            write(K % x == 0);
        else
            write(K / max(x, y));
        putch('\n');
    }
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话