【不是钓鱼！】万能的s1，求个算法最优解的题,附上题目

asddddad

有26个箱子排一列，里面各有一个包裹，包裹上贴有a-z的标签，不重复但是随机打乱，一次只能打开一个箱子，箱子从外面看上去是一样的，问: 如何用最高效的方法找到有b标签的箱子

董卓

这能有个p算法啊……不就是随机么

Onelooker

贴有b的箱子举手

5long

把箱子换成透明材料的, 可以直接看到里面的标签.

Tring

要么就像楼上说的，让贴了B的包裹自己举手喊到。
如果不开箱子认不出包裹的话，就同时把所有箱子一起打开一起看包裹。
如果一次只能开一个箱子认一个包裹的话，随机为完全随机均匀分布，那不管用什么顺序拆开看，需要的次数都符合正态分布，期望为13.5次。

Lunamos

既然说是包裹，那箱子就假设是亚马逊那种电商常用的纸箱。
一般人装箱打包时是按顺序写的。所以写A、B、C的时候装箱工人还比较有耐心，箱子封装得比较漂亮。
到X、Y、Z的时候已经疯了，不知道自己干这个有啥意义，箱子封得比较潦草。
所以可以找那些看起来外观看起来没有体现太多戾气的箱子，字母顺序靠前的概率比较大。
（一本正经地胡说八道）

咲蛍

这还能咋快，一个一个拆吧

hein

PC区终于有自己独特的钓鱼贴了

暗铁

你这也不像算法题啊，连个输入输出都没有

Lunamos

LZ居然补充了题目要求……LZ原本题目没说全，寻找某包裹的需求是有很多次而不是一次，箱子也是可以排列的。

那就把箱子排序呗，第一次就是逐个打开看，在纸上排序之后吩咐人去按照编号映射搬箱子。之后每次就直接处理了。

如果没有notepad，可以用置换的方法归位。从第一个箱子开始，打开看到字母，与该字母顺位的箱子交换。如果当前处理的箱子i无需交换，则继续处理i+1，直到i=26。这就不需要用笔记本了。

asddddad

Lunamos 发表于 2021-9-22 22:37
LZ居然补充了题目要求……LZ原本题目没说全，寻找某包裹的需求是有很多次而不是一次，箱子也是可以排列的。 ...

感谢，就是这个!

5long

虽说用一个虚构的环境来锻炼思维能力也不是不可以
但过于魔法的设定让人无法联想到现实工作条件
锻炼出来的思维能力不知道有什么用
确定写这书的人不是在给竞争对手做培训?

谁家的物流管理能不让在箱子上做记号? 贴个便利帖都不行?
每拿走一个 A 包裹, 箱子就会魔法地 refill 包裹, 那我能不能直接找补货的法师要货? 还搁这开盲盒呢?
还附加条件说不能用 notepad 来增加难度. Do you guys not have phones?

Tring

完整题目最重要的一个条件是可以互换移动盒子，而且任务是反复进行的，并不是只有一次查找任务。
禁止直接标注盒子的意思就是，禁止使用一切类似哈希表的算法。
简单来说这就是一个查找和排序的组合题，在随机查找的过程中逐渐完成一个排序。


所以算法大致可以抽象成这样一种形式：
每一次随机访问，如果没有得到正在搜寻的目标，则得知一个单元信息，并根据信息进行一次排序操作；如果得到了正在搜寻的目标，则返回结果并进行一次排序，然后结束本次查找。

这里和真正的排序题最大的区别在于，有时候查找任务并不需要将整个序列进行完整排序，甚至不需要得知所有箱子的信息。

为了符合这个思想，我选择了一种以置换群的轮换表示为基础的方法来解决这个问题。这当然不太可能是最好的方法，但是应该是最直观能想到的方法。

由于任意有限置换群都可以表示成轮换形式，这里举个6个元素（6个箱子）的例子。考虑数值比字母更直观，因此后面都用数字表示。
（1，2，3，4，5，6）
的一个随机置换
（3，6，4，1，5，2）
可以表示为轮换：
（1 3 4）（2 6）（5）
这时这6个元素相当于被分为了3个轮换组。

假设这个随机置换的顺序就是初始箱子的排序，且不为解题人所知，表示为
（X，X，X，X，X，X）
再假设第一次的搜索任务要求搜索标签3。

我们首先能确定的一点是，3这个元素所在的轮换组，一定会占有第3个位置。
因此无疑应该先去看第3个箱子里放了啥，翻开后得到
（X，X，4，X，X，X）

下一步，完成当前这个轮换组的排序，将其轮换到原本的顺序：
拿起标着4的箱子，翻开第4格的箱子，查看内容并拿起，然后重复这一步直到一个轮换组调整完成
（X，X，O，1，X，X） 4
（3，X，O，4，X，X） 1
（1，X，O，4，X，X） 3
（1，X，3，4，X，X）

这样，就完成了第一个轮换组的调整，找到了标签3的箱子，并且将1，3，4这3个组内的箱子调整到了正确的位置。
将这3个标签记录在你的本子上，以后的搜索任务如果是在1，3，4中的一个，则可以不再进行任何查找或者移动，直接完成。

如果后续的查找任务，并不在已经完成轮换的编号中，则再重复上面的轮换操作，完成新的组，直到把3个组全部轮换完成，6个箱子的排序将变为顺序排序。

asddddad

Tring 发表于 2021-9-23 01:21
完整题目最重要的一个条件是可以互换移动盒子，而且任务是反复进行的，并不是只有一次查找任务。
禁止直接 ...

牛哇大佬

Tring

asddddad 发表于 2021-9-23 01:55
牛哇大佬

上述方法如果从工人视角来说的话，还可以描述的简单一点，不用本子记录也行。

对于搜索标签n（使用数字标签而非字母）的任务：

1，拿起第n个箱子。
2，检查手里的箱子，如果是标签n，则将手里的箱子放回空格处，完成本次任务；如果是标签m（m不为n），则继续后续步骤。
3，将手里的箱子和第m个箱子交换。
4，回到第2步。

asddddad

Tring 发表于 2021-9-23 03:45
上述方法如果从工人视角来说的话，还可以描述的简单一点，不用本子记录也行。

对于搜索标签n（使用数字 ...

好的，我基本理解了

Lunamos

Tring 发表于 2021-9-23 02:21
完整题目最重要的一个条件是可以互换移动盒子，而且任务是反复进行的，并不是只有一次查找任务。
禁止直接 ...

题目描述倒是有一个地方不大清楚，说不同需求一天内源源不断的情况下，make parcel finding as effective as possible。就总觉得是事先准备好结构，尽量优化搜索的响应时间。但这就有些码农思维了。
做题思维的话就是单次响应可以长，总时间短即可，这就确实只需一个在线的排序过程就好，不用排完。

大暴死

Tring 发表于 2021-9-23 03:45
上述方法如果从工人视角来说的话，还可以描述的简单一点，不用本子记录也行。

对于搜索标签n（使用数字 ...

我就觉得这题很人力资源机器

—— 来自 Xiaomi M2102K1C, Android 11上的 S1Next-鹅版 v2.4.4.1