题目大意
给你一个数字 \(N\)，现在希望你用三个数字 \(1,A,B\) 拼出 \(N\)。
但是使用一次 \(1\) 要花掉 \(X\) 元，用一次 \(A\) 花掉 \(Y\) 元，用一次 \(B\) 花掉 \(Z\) 元。
请你求出最小的花费。
思路
我们钦定 \(a\) 的性价比不低于 \(b\)，如果不满足就交换。
最多只能取 \(\left\lfloor \dfrac{n}{a} \right\rfloor\) 个 \(a\)，最多只能取 \(a-1\) 个 \(b\)。如果选 \(a\) 个 \(b\) 的话，我们完全可以用 \(b\) 个 \(a\) 来代替它，这样不是更优的，所以 \(b\) 最多取 \(a-1\) 个。
于是有策略：
- 如果 \(a \leq \sqrt{n}\)，那么我们枚举 \(b\) 的数量；
- 如果 \(a \geq \sqrt{n}\)，那么就有 \(\left\lfloor \frac{n}{a} \right\rfloor \leq \sqrt{n}\)，就枚举 \(a\) 的数量。
这两种方法枚举次数都不超过 \(\sqrt{n}\)，所以时间复杂度约为 \(\operatorname{O}(\sqrt{n})\)。
Code
#include <bits/stdc++.h>
using namespace std;
int T;
long long n,a,b,x,y,z;
long long ans,tmp;
double val1,val2,val3;
void Work() {
ans = LLONG_MAX;
if(a * z < y * b) {
swap(a,b);
swap(y,z);
}
if(a * x <= y) {
ans = n * x;
return ;
}
if(b * x <= z) {
ans = n / a * y + n % a * x;
return ;
}
if(n / a < a - 1) {
for(int i = 0;i <= (n / a); i++) {
tmp = n - i * a;
ans = min(ans,i * y + tmp / b * z + tmp % b * x);
}
}
else {
for(int i = 0;i <= a - 1; i++) {
tmp = n - i * b;
if(tmp >= 0)
ans = min(ans,i * z + tmp / a * y + tmp % a * x);
}
}
return ;
}
int main() {
#ifdef ONLINE_JUDGE == 1
freopen("cs.in","r",stdin);
freopen("cs.out","w",stdout);
#endif
scanf("%d",&T);
while(T--) {
cin >> n >> a >> b >> x >> y >> z;
Work();
cout << ans << "\n";
}
fclose(stdin);
fclose(stdout);
return 0;
}