ARC 题解列表

一道很好的根分题，所以单独拉一个题解出来记录。

显然如果用 $1$ 填 $a,b$ 更优，可以先让贡献最小化，即 $y = \min(y, a \times x)$，$z = \min(z, b \times x)$。
然后让 $\frac{a}{y} \gt \frac{b}{z}$，即让 $a$ 的性价比更高。

1. 接着会发现，对 $a$ 的加入操作至多进行 $\lfloor \frac{n}{a} \rfloor$ 次。
2. 而 $b$ 加入至多 $a-1$ 次，因为如果加入 $a$ 次 $b$，不如加入 $b$ 次 $a$ 让代价更小。

然后 $n$ 非常大，所以考虑怎么降低复杂度。
注意到第一种情况我们只需要枚举 $\lfloor \frac{n}{a} \rfloor$ 次，第二种只需要枚举 $a-1$ 次。
一个是 $\frac{n}{a}$ 级别，一个是 $a$ 级别。

这里加入 根号分治 肯定是最优的。所以：
- 若 $a \gt \sqrt{n}$，用第一种方法。
- 否则用第二种。

时间复杂度即 $O(T \sqrt{n})$，可以通过。

#include <bits/stdc++.h>
using namespace std;
int T;
long long n, a, b, x, y, z;
long long ans = 0;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld%lld%lld%lld", &n, &a, &b, &x, &y, &z);
        ans = n * x;    //答案下界！！！
        y = min(y, a * x), z = min(z, b * x);
        if (a * z < b * y) swap(a, b), swap(y, z);  //精度
        if (a * a > n) {    //枚举 a 出现次数
            for (long long i = 0; i <= n / a; i++) {
                long long p = n - i * a;
                if (p < 0) break;
                ans = min(ans, i * 1ll * y + (p / b) * 1ll * z + (p % b) * 1ll * x);
            }
        } else {    //枚举 b 出现次数
            for (long long i = 0; i <= a - 1; i++) {
                long long p = n - i * b;
                if (p < 0) break;
                ans = min(ans, i * 1ll * z + (p / a) * 1ll * y + (p % a) * 1ll * x);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}