题目描述与示例

题目描述

求从坐标零点到坐标点n的最小步数，一次只能沿横坐标轴向左或向右移动2 或3

注意：途径的坐标点可以为负数

输入描述

坐标点n

输出描述

输出从坐标零点移动到坐标点n的最小步数

备注1 <= n <= 10^9

示例一

输入

输出

说明

从坐标零点移动到4，最小需要两步，即右移2，再右移2

解题思路

由于步长可以选择2或3，为了使得步数尽可能地少，我们必然会贪心地尽可能多地选择走3步。譬如要到达坐标为24的位置，我们会选择走8次3步，而不会选择走12次2步或者混合两种步长。

观察题目，列出一些特殊情况并总结规律。当

n为3的倍数。显然向右走n//3步就可以到达n，而且n//3一定是最小步数。
n = 1。那么至少需要走两次，向右走3步，向左走2步。
n > 1，且n % 3 = 2。由于n除以3余2，那么前n-2步我们可以均用步长3来填充，一共需要走n//3步，最后再走2步。这样总的步数为 n``//3+1。
n > 1，且n % 3 = 1。这是最棘手的一种情况。
1. 考虑n = 4，只需走2次2步即可到达。一共2步。
2. 考虑n = 7，可以先走1次3步，再走2次2步。一共3步。
3. 考虑n = 10，可以先走2次3步，再走2次2步。一共4步。
4. 显然，对于这种情况，前n-4步我们可以均用步长3来填充，一共需要走n//3-1步，最后剩余4步的距离，走2次2步。这样总的步数为n``//3+1。

上述的3和4可以合并为一种答案，故仅需对n的大小做三种不同的判断即可计算出答案。

代码

Python

# 题目：2023B-求最少步数
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：贪心
# 代码看不懂的地方，请直接在群上提问


n = int(input())
# 分三种情况讨论
if n == 1:
    print(2)
elif n % 3 == 0:
    print(n//3)
else:
    print(n//3 + 1)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        if (n == 1) {
            System.out.println(2);
        } else if (n % 3 == 0) {
            System.out.println(n / 3);
        } else {
            System.out.println(n / 3 + 1);
        }
    }
}

C++

“`C++
#include <iostream>

using namespace std;

int main() {
int n;
cin >> n;

<pre><code>if (n == 1) {
cout << 2 << endl;
} else if (n % 3 == 0) {
cout << n / 3 << endl;
} else {
cout << n / 3 + 1 << endl;
}

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(``1``)。仅需常数级别运算。

空间复杂度：O(``1``)。仅需常数级别变量。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）