首页 > 试题广场 >

太阳系DISCO

[编程题]太阳系DISCO
  • 热度指数：1874 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
{\hspace{15pt}}在一个平行世界的太阳系中，所有行星恰好构成一个长度为 n 的环，按顺时针依次编号为 1,2,\dots ,n。相邻两颗行星间距离相等，且保证 n 为偶数。

{\hspace{15pt}}你位于编号为 a 的行星，目标是到达编号为 b 的行星。你可以执行以下三种操作，每次操作均消耗 1 个单位时间：
{\hspace{23pt}}\bullet\,顺时针移动 x 颗行星；
{\hspace{23pt}}\bullet\,逆时针移动 y 颗行星；
{\hspace{23pt}}\bullet\,发动一次传送技能（最多可使用 k 次），将你顺时针移动 \tfrac{n}{2} 颗行星，即跳到正对面的那颗行星。

{\hspace{15pt}}请你计算，从 a 行星移动到 b 行星的最少时间；若无论如何都无法到达，则输出 -1。

输入描述:
{\hspace{15pt}}在一行上输入 6 个整数 n,k,a,b,x,y，含义分别为：
{\hspace{23pt}}\bullet\,n\left(2 \leqq n \leqq 2\times 10^{5}\right)——行星数量，且 n 为偶数；
{\hspace{23pt}}\bullet\,k\left(0 \leqq k \leqq 2\times 10^{5}\right)——技能可使用的最大次数；
{\hspace{23pt}}\bullet\,a,b\left(1 \leqq a,b \leqq n\right)——起点与终点的编号；
{\hspace{23pt}}\bullet\,x,y\left(1 \leqq x,y \leqq n\right)——每次普通移动的距离。


输出描述:
{\hspace{15pt}}输出一个整数，表示最少所需时间；若无法到达，则输出 -1。
示例1

输入

4 0 1 2 2 1

输出

2

说明

你可以先顺时针移动 x=2 颗行星到达编号 3，再逆时针移动 y=1 颗行星到达编号 2，共耗时 2。
示例2

输入

4 114514 1 3 1 1

输出

1
示例3

输入

4 114514 1 2 2 2

输出

-1

备注:

算法知识视频讲解
添加回答
Java
美丽的咸鱼喜欢摸鱼头像 美丽的咸鱼喜欢摸鱼
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static class Node{
        int pos;
        int used;
        int cost;
        public Node(int pos, int used, int cost){
            this.pos = pos;
            this.used = used;
            this.cost = cost;

        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();

        int start = a - 1;
        int end = b - 1;
        int tpCost = n / 2;

        if(start == end){
            System.out.print(0);
            return;
        }

        Queue<Node> q = new LinkedList<>();
        int effectiveK = Math.min(k, 1);
        boolean visited[][] = new boolean[n][effectiveK + 1];
        visited[start][0] = true;
        q.offer(new Node(start, 0, 0));

        while(!q.isEmpty()){
            Node curr = q.poll();

            int nextPos1 = (curr.pos + x) % n;
            if(nextPos1 == end){
                System.out.print(curr.cost + 1);
                return;
            }

            if(!visited[nextPos1][curr.used]){
                visited[nextPos1][curr.used] = true;
                q.offer(new Node(nextPos1, curr.used, curr.cost + 1));
            }

            int nextPos2 = (curr.pos - y + n) % n;
            if(nextPos2 == end){
                System.out.print(curr.cost + 1);
                return;
            }

            if(!visited[nextPos2][curr.used]){
                visited[nextPos2][curr.used] = true;
                q.offer(new Node(nextPos2, curr.used, curr.cost + 1));
            }

            if(curr.used < effectiveK){
                int nextPos3 = (curr.pos + tpCost) % n;
                if(nextPos3 == end){
                    System.out.print(curr.cost + 1);
                    return;
                }

                if(!visited[nextPos3][curr.used + 1]){
                    visited[nextPos3][curr.used + 1] = true;
                    q.offer(new Node(nextPos3, curr.used + 1, curr.cost + 1));
                }
            }
        }
        System.out.print(-1);
    }
}
发表于 2026-05-04 16:55:29 回复(0)
提交观点

问题信息

广度优先搜索(BFS)
来自：华为机试编程模拟题10
难度：
1条回答 1727浏览

热门推荐

相关试题

太阳系DISCO

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号