所以,我有这样的作业:
给定两个可以达到long long
限制的数n
和k
,我们做这样的操作:
- 如果
n
可以被k
整除,则分配n = n/k
- 如果
n
不能被k
整除,则将n
减少1
找到从 n
到 0
的最小操作数。
这是我的解决方案
#define ll long long
ll smallestSteps(ll n, ll k) {
int steps = 0;
if (n < k) return n;
else if (n == k) return 2;
else {
while (n != 0) {
if (n % k == 0) {
n /= k;
steps++;
}
else {
n--;
steps++;
}
}
return (ll)steps;
}
}
我认为这个解决方案是O(n/k)
?
但我认为n
和k
可能非常大,因此程序可能会超过1s的时间限制。有没有更好的方法来做到这一点?
编辑 1:我使用 ll
来缩短
最佳答案
根据这些观察结果可以改进算法:
- 如果
n<k
然后k|(n-m)
永远不会对任何正的 m 成立。所以答案是n
步骤。 - 如果
(k|n)
不持有那么最大的数字m, m<n
它所做的是n - (n%k)
.所以需要n%k
步直到 (k|m) 再次成立。
实际上,您只需要使用 std::div
继续对余数进行除法运算即可(或依赖编译器优化)并增加步数+1。
steps=0
while(n>0)
mod = n%k
n = n/k
steps+=mod + 1
return steps
关于c++ - 从数字到 0 最快的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56463164/