将一系列旋转拨盘设置为给定序列的最少步骤 [英] Minimum steps to set a series of rotating dials to a given sequence

问题描述

所以我有以下问题: 有n个旋转拨盘，每个拨盘设置为介于0到9之间的某个数字，并且它们需要与另一组n个数字(也位于0到9之间)匹配.

旋转的步骤是向上或向下旋转任何数量的连续刻度盘.刻度盘环绕9.也就是说，将刻度盘从9向上旋转1会得到0，反之亦然.

我需要找到使初始配置与给定配置相匹配的最小步骤数.

例如:Initial -> 154 Given -> 562

1.首先移动第一个2拨号按1 154 -> 264-> 1步
2.向上移动第一个拨盘3 264->564-> 3步
3.向下移动3rd转盘2 564->562-> 2步
所以最小步长是6.
我不需要代码，只需一些方法的见解即可.

So I have the following problem: There are n rotating dials each set to some number between 0-9 and they need to be matched with another series of n numbers(also between 0-9).

One step of rotation is rotating any number of consecutive dials up or down by one step. The dials wrap around 9. i.e. rotating one step up from 9 gives 0 and vice versa.

I need to find the minimum number of steps to match the initial configuration with the given configuration.

Ex: Initial -> 154 Given -> 562

1. first move first 2 dials up by 1 154 -> 264->1 step
2. move 1st dial 3 up 264->564 ->3 steps
3. move 3rd dial 2 down 564->562 ->2 steps
So min steps is 6.
I don't need the code, only some insights to the approach.

推荐答案

我不确定我是否正确理解了该问题.看来，如果您将两个数字一起旋转1步，那么该移动仅算作一个移动，而不是两个，对吗?

I'm not sure if I understand correctly the problem. It seems that if you rotate two numbers together 1 step, that move is counted only as one move, not two, correct?

在这种情况下，为什么不计算每个数字与其另一个系列中的匹配之间的最小距离.在该组之后，减号和加号一起移动，并尽可能将数字一起移动.

In that case why not count the minimum distance between every number and its match in the other series. After that group together minus moves and plus moves, and move the numbers together where possible.

例如:

145-> 632

145 -> 632

• 1的最小距离为5 +-(向上或向下)
• 4的最小距离为1-
• 5的最小距离为3-

由于只有减号，所以我将5也算作减号，然后执行以下操作:

Since there only are minus moves, I would count the 5 also as a minus move, and do following:

1. 将所有数字向下移动-> 034
2. 将第一个和最后一个数字向下移动两步-> 832
3. 将最后一个数字向下移动两步-> 632 =共5个步骤

1. move all numbers down one step -> 034
2. move first and last number down two steps -> 832
3. move last number down two steps -> 632 = total 5 steps

这篇关于将一系列旋转拨盘设置为给定序列的最少步骤的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！