算法
(二分) $O(\log 10^9)$
记 $f(N)$ 为整数 $N$ 的价格
由题意可知,$f(N) = A \times N + B \times d(N)$
容易发现,$Ax$ 严格单调递增, $Bd(x)$ 单调递增,故 $f(N)$ 满足二段性。所以我们可以考虑二分 $N$。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
int main() {
ll a, b, x;
cin >> a >> b >> x;
auto d = [&](ll n) {
int res = 0;
while (n) {
n /= 10;
++res;
}
return res;
};
auto f = [&](ll n) {
return a * n + b * d(n);
};
ll ac = 0, wa = 1000000001; // ac: o, wa: x
while (ac + 1 < wa) {
ll wj = (ac + wa) / 2;
if (f(wj) <= x) ac = wj; else wa = wj;
}
cout << ac << '\n';
return 0;
}