更衣室算法 [英] Locker Room Algorithm
问题描述
注意：请注意，这不是我学校的作业，因为我本人甚至都不知道哪个学校写了这个问题。希望不会发生误会。
Note: Just to give a heads up, this is not an assignment for my school since I myself don't even know which school wrote this question. Hopefully no misunderstanding occurred.
我发现了一个有关更衣室的有趣问题：
I found this interesting questions about locker room:
Rec的更衣室有N个更衣室，分别标记为1、2，...。 。 。，N。
The locker room of the Rec has N lockers that are labeled 1, 2, . . ., N .
每个储物柜均已锁定，但可以使用其唯一钥匙打开。
Each locker is locked, but can be opened using its unique key.
每个储物柜的钥匙副本位于其相邻的储物柜中；例如，储物柜i的钥匙的
副本放置在储物柜i +1和i − 1中（储物柜1的
钥匙仅在储物柜2中，而储物柜N的钥匙仅在$ b中$ b储物柜N-1）。
Copies of the key to each locker are in its adjacent lockers; i.e. a copy of the key to locker i is placed in locker i + 1 and i − 1 (the key to locker 1 is only in locker 2 and the key to locker N is only in locker N − 1).
T网球位于T个不同的储物柜中（您
知道它们位于哪个储物柜中）。您将获得M个
个储物柜的钥匙，并且您的目标是通过
打开最少数量的储物柜来收集所有网球。
T tennis balls are inside T distinct lockers (and you know which of the lockers they are in). You are given keys to M of the lockers and your goal is to collect all of the tennis balls by opening the least number of lockers.
对于图片，您可以直接在此处的文件中查看
For pictures you can see it directly to the file here.
我必须将这个问题交给新生，但我想确保首先我自己已经有正确的答案。
I have to give this questions to some freshman but I wanted to make sure first that I myself already have the correct answer beforehand.
我在想的是：
-
需要逐个检查球。因此，对于每个球（忽略其他球），必须遍历指定的球来访问每个键。对于每个键，计算访问球所需的步骤。最小的结果存储在一个称为总步长的变量中。
Need to check the ball one by one. So for each ball (ignore the other balls), each key have to visit by traversing to the designated ball. For each key, calculate the steps it takes to visit the ball. The smallest result is stored in an variable called "total steps".
对下一个球执行此精确操作，当我得到当前当前的最小步数时球。我将此值添加到总步长。
Do this exact thing to the next ball and when I get the minimum steps for this current ball. I add this value to "total steps".
如果在键上方有一个球，则应用特殊条件，然后键从i + 1和i开始遍历-1。
Special condition applied if there is a ball above the key, then key start traversing from i + 1 and i - 1.
我的问题是：对吗？我不想与其他人分享错误的算法，因为它不专业。
My question is: am I right? I don't want to share the wrong algorithm to others since it's unprofessional. Looking forward to any comments, suggestions and inputs.
推荐答案
您的算法将不会导致最少的步骤。您不能独立考虑球。让我们考虑以下情况：您只有一个用于1号储物柜的钥匙，球在12、10、8、6、4、2储物柜中。如果按我给的顺序考虑球，则总步数将结束等于 11 + 9 + 7 + 5 + 3 +1 ，而您可以一次通过11个步骤来解决问题。您不应该忽略前面步骤中访问的框。
Your algorithm will not result in minimum number of steps. You can not consider balls independently. Lets consider the following case: You have only one key for locker number 1 and balls are in lockers 12, 10, 8, 6, 4, 2. If You consider the balls in the order I have given you will end up with total steps equal to 11 + 9 + 7 + 5 + 3 + 1, while you can solve the problem in a single pass of 11 steps. You should not ignore the boxes visited on the previous steps.
这篇关于更衣室算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
