From Hero to Zero
发布时间
阅读量：
阅读量
From Hero to Zero
某天早晨，
小明向你提供了两个数值 n 和 k。
你需要对数值 n 执行一次操作：
在每次操作中，
你可以选择以下两种方式之一：
- 将数值 n 减少 1
- 当数值 n 能够被k整除时，
则可执行n/k的操作
例如 n = 27, k = 3 的情况下：你可以完成以下操作：将数字逐步减少至零的方式有多种路径（不一定是最优的选择哦~）。请计算出数字 n 变为 0 所需的最少操作次数。
输入格式
第一行输入一个整数 t (1 \leq t \leq 100)，表示数据个数
接下来 t 行，每行 2 个整数 n 和 k (1 \leq n \leq 10^{18}, 2 \leq k \leq 10^{18})
输出格式
将数字 n 变为 0 的最小次数
样例
样例输入
2
59 3
1000000000000000000 10样例输出
8
19样例解释
对于第一组数据，有：59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0
对于第二组数据，可以连续除以 18 个 0 使变为 1。
分析
这道题最容易想到的就是模拟了。
代码如下：
#include <cstdio>
int T;
long long N, K;
long long ans;
int main()
{
scanf("%d", &T);
for (int i = 1; i <= T; i++)
{
scanf("%lld %lld", &N, &K);
ans = 0;
while (N)
{
if (N % K == 0) N /= K;
else --N;
++ans;
}
printf("%lld\n", ans);
}
return 0;
}但使用模拟方法会导致该问题的时间效率不足。然而由于其计算复杂度过高 当n = pk + q 时 我们需要循环n-1共q次 这样的时间复杂度为q\为了避免这种情况 我们建议采取改进措施：即直接计算n - q\此时的时间复杂度为1 这明显优于之前的情况
正解代码如下：
#include <cstdio>
int T;
long long N, K;
long long ans;
int main()
{
scanf("%d", &T);
for (int i = 1; i <= T; i++)
{
scanf("%lld %lld", &N, &K);
ans = 0;
while (N)
{
if (N % K == 0) ++ans, N /= K;
else ans += N % K, N -= N % K;
}
printf("%lld\n", ans);
}
return 0;
}全部评论 (0)
还没有任何评论哟~