目的地最短步数

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T;
    while (cin >> T) {
        int sum = 0, i = 0;
        while (sum < T) sum += ++i;
        cout << i + (((sum - T) % 2 == 0) ? 0 : ((i + 1) % 2 == 1) ? 1 : 2) << endl;
    }
    return 0;
}

"""
广度优先遍历算法
[0]             第0层，
[1, -1]         第1层，上层的结果 +1，-1
[3, -1, 1, -3]  第2层，上层的结果 +2，-2
...             第i层，上层的结果 +i，-i
"""
def BFS(n):
    bfs = set([0])
    i = 0
    while True:
        i += 1
        pre = bfs.copy()
        bfs = set()
        for num in pre:
            if num+i==n or num-i==n:
                return i
            else:
                bfs.add(num+i)
                bfs.add(num-i)
n = int(input())
print(BFS(n))

https://leetcode.com/problems/reach-a-number/

这道题是 leetcode 754 原题

//先一直向前走，使得sum>=target，如果步数小于这个数是不可能到达的
//当sum>target后，再考虑能否将之前的步伐反向来恰好到达目的地
//也就是说，从最小的可能步数出发，每次加一并检查是否可行

public int reachNumber(int target) {  int step = 0;
    int sum = 0;
    while(sum<target){
        step++;
        sum += step;
    }
    //此时sum>=target
    //sum==target的话不用说，很完美
    //sum>target的话，就要考虑，能不能之前走过的某一步改为向后倒退
    //倒退操作会使得 sum-even_number    （这个even number = 2*该步步长）
    //如果(sum-target)%2==0,就说明sum多出来的长度，可以通过将之前的 向前的步伐 改为 向后的步伐 来使得sum==target
    //但是, (sum-target)%2可能不为0，此时不能通过改变步伐方向来完成。意味着我们需要再往前走（最多再走两次）
    while( (sum-target)%2!=0 ){
        step++;
        sum += step;
    }
    return step;
}
//后续：为什么说最多再走两次？
//首先， (sum-target)为奇数才需要继续走
//下一次步长可能为奇数或者偶数，如果为奇数，那么就完成了，此时（sum-target)%2==0
//                             如果为偶数，此时（sum-target）仍然是奇数，但是再下一次步长为奇数，此时（sum-target)%2==0

import java.util.*;

public class Main{

    public static int reachNumber(int target) {  
        int step = 0;
        int sum = 0;
        while(sum<target){
            step++;
            sum += step;
        }
        while( (sum-target)%2!=0 ){
            step++;
            sum += step;
        }
        return step;
    }
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int step = reachNumber(n);
        System.out.println(step);
    }
}

#include <iostream>
#include <deque>
#include <unordered_set>

using namespace std;

int bfs(int target) {
  deque<int> q{{0}};
  
  int steps = 0;
  while (not q.empty()) {
    size_t s = q.size();
    while (s--) {
      int curr = q.front(); q.pop_front();
      if (curr == target) return steps;
      for (int nxt : {curr - steps - 1, curr + steps + 1}) {
        q.emplace_back(nxt);
      }
    }
    ++steps;
  }
  
  return -1;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int t;
  cin >> t;
  cout << bfs(t);
  return 0;
}

#include "iostream"
#include "vector"
#include "algorithm"
#include "set"
using namespace std;


int dfs(int n) {
	vector<set<int>> s(2);
	int d = 0;    //奇偶层, 这样避免了拷贝的麻烦
	int i = 0;
	s[1 - d].insert(0);
	while (1) {
		i += 1;
		for (int num : s[1 - d]) {
			if (num + i == n || num - i == n) {
				return i;
			}
			else {
				s[d].insert(num + i);
				s[d].insert(num - i);
			}
		}
		
		d = 1 - d;
		s[d].clear();
	}
}
int main() {
	int t;
	cin >> t;
	int step = dfs(t);
	 

		
	cout << step << endl;
	system("pause");
	return 0;
}

极其暴力的广度优先搜索,可能会带坏小孩子

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static int func(int T){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        for(int i=1;i<Integer.MAX_VALUE;i++){
            int size = queue.size();
            for(int j=0;j<size;j++){
                int num = queue.poll();
                if(num==T) return i-1;
                queue.add(num+i);
                queue.add(num-i);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        System.out.println(func(T));
    }
}

a,i,j = int(input()),1,2
while i < a&nbs***bsp;(i + a) % 2:
    i,j = i + j,j + 1
print(j - 1)

如果贪心想不到，BFS还能续一波命

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import static java.lang.System.in;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();
        que.add(new Node(0, 0));
        //bfs搜索
        Node temp;
        int ans = 0;
        while (true) {
            temp = que.poll();
            if (temp.pos == n) {
                ans = temp.times;
                break;
            }
            que.offer(new Node(temp.pos + temp.times + 1, temp.times + 1));
            que.offer(new Node(temp.pos - temp.times - 1, temp.times + 1));
        }
        System.out.println(ans);
    }
    public static Queue<Node> que = new LinkedList();
    private static class Node{
        int pos;
        int times;
        public Node(int pos, int times) {
            this.pos = pos;
            this.times = times;
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

struct P{
    int x, t, s;
    P(int x, int t, int s):x(x),t(t),s(s){}
};

int BFS(int T){
    queue<P> q;
    q.push(P(0,0,1));
    while(!q.empty()){
        P p = q.front();
        q.pop();
        if(p.x == T)
            return p.t;
        q.push(P(p.x+p.s, p.t+1, p.s+1));
        q.push(P(p.x-p.s, p.t+1, p.s+1));
    }
    return -1;
}

int main(){
    int T;
    while(cin>>T)
        cout<<BFS(T)<<endl;
    return 0;
} 

#include <cstdio>  using namespace std;  int main() { int n, ans = 0;  scanf("%d", &n);  for (int i = 1;; i++) {
        ans += i;  if (ans >= n && (ans - n) % 2 == 0) {
            printf("%d\n", i);  break;  }
    } return 0; }

#include <iostream>
using namespace std;
int main(void){
    int T, i, sum = 1;
    cin>>T;
    for(i = 2; (sum-T)&1 || sum < T ; ++i)
        sum += i;
    cout<<i-1<<endl;
    return 0;
}

1. T和sum同奇偶
2. sum≥T

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 只要 sum 比 target 大，而且差值为偶数就可以了；
 * 假设a为正向移动步数，b为负向移动步数，有 a - b = target，sum = a+b；
 * 则有 sum - target == 2b;故sum与b成正比
 * 一定是可以走到的：因为 反一步+ 正一步 步长加一
 */
public class Solution14_目的地的最短步数 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int sum = 0;
        int step = 1;
        while (n > sum || (sum - n) % 2 != 0) {
            sum += step;
            step++;
        }
        System.out.println(step - 1);
    }
}

• 层次遍历，每次有加和减i两个选项，将其结果送到队列中。
• 使用层次遍历的原因：方便设定终止条件，如果当前层所有的位置和下一步的步数和都大于N的话，就再也不会走到指定的位置了。

from collections import deque
N = int(input())

que = deque([(0,1)])
while que:
    # 标记当前层是不是还有小于N的值
    SMALLER = False
    for _ in range(len(que)):
        cur_pos,step = que.popleft()
        if cur_pos == N:
            print(step-1)
            exit()
        if cur_pos+ step <= N:
            SMALLER = True
        que.append([cur_pos+step,step+1])
        que.append([cur_pos-step,step+1])
    if not SMALLER:
        print(-1)
        break

#include<iostream>
#include<queue>
using namespace std;
int cur_num = 0;
int num_steps =0;
queue<int> q;
int bfs(int target)
{
    q.push(0);
    int step = 1;
    while(!q.empty())
    {
        int tmp_n = q.size();
        for(int i = 0;i<tmp_n;i++)
        {
            int tmp = q.front();
            q.pop();
            if(tmp == target)
                return step-1;
            q.push(tmp+step);
            q.push(tmp-step);
        }
        step++;
    }
    return -1;
}
int main()
{
    int target;
    cin>>target;
    int ans = bfs(target);
    cout<<ans<<endl;
    return 0;
}

//BFS
#include<iostream>
(720)#include<queue>

using namespace std;

int main(void) {
	int N;
	int step = 1;
	cin >> N;
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int n = q.size();
		for (int i = 0; i < n; i++) {
			int index = q.front();
			q.pop();
			if (index + step == N) {
				cout << step << endl;
				
				return 0;
			}
			
			
			q.push(index + step);

			if (index - step == N) {
				cout << step << endl;
				
				return 0;
			}
			
			
			
			q.push(index - step);
			
		}
		step++;
	}
	cout << -1 << endl;
	
	return 0;
}