解题思路

这是一个路径规划问题。关键点如下：

  1. 每次只能向前或向后走
  2. 第N次行走必须走N步
  3. 需要计算到达目标的最少步数

解题思路：

  1. 观察规律可以发现：
    • 每一步可以选择向前或向后，相当于给每一步的步数加正号或负号
    • 最终的和需要等于目标距离
    • 最终和与目标距离必须同奇偶性
  2. 从第1步开始累加，直到：
    • 累加和大于等于目标距离
    • 且累加和与目标距离同奇偶性

代码

#include <iostream>
using namespace std;

int main() {
    int target;
    cin >> target;
    
    int sum = 0;
    int steps = 1;
    
    // 累加直到满足条件
    while ((sum - target) % 2 == 1 || sum < target) {
        sum += steps;
        steps++;
    }
    
    cout << steps - 1 << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int target = scanner.nextInt();
        
        int sum = 0;
        int steps = 1;
        
        // 累加直到满足条件
        while ((sum - target) % 2 == 1 || sum < target) {
            sum += steps;
            steps++;
        }
        
        System.out.println(steps - 1);
    }
}

target = int(input())
sum = 0
steps = 1

# 累加直到满足条件
while (sum - target) % 2 == 1 or sum < target:
    sum += steps
    steps += 1

print(steps - 1)

算法及复杂度

  • 算法：数学
  • 时间复杂度： - 为目标距离，因为累加和是等差数列
  • 空间复杂度： - 只使用常数额外空间