谁帮我解答 速度 给高分
发布网友
发布时间：2023-02-03 01:43
共2个回答
热心网友
时间：2024-11-03 20:10
既然*每天随便选择一个房间搜查，还怎样为*设计一个100%能抓到小偷的方案，要求所用时间最短？
热心网友
时间：2024-11-03 20:11
规律要点：
1小偷必须移动一个房间，而*可以连续搜查同一个房间；
2如果*也是每次搜查相邻房间，小偷与*的距离的奇偶性始终不变；
3如果*连续两次搜查同一间房间，奇偶性逆转；
4当*从2号开始，依次搜查至n-1号过程中，若小偷想从大号房间（即*右侧）走到小号房间（即*左侧），则一开始与*间隔的房间数（以下称距离）需为偶数;（交换时*从m→m+1,小偷从m+1→m）
5小偷没有机会从左侧越到右侧；
6如果小偷始终没有越过*，则在2→n-1,n-1→2的过程中，必然被发现。
原因如下，我们只考虑最坏情况，即小偷运气特别好，不到最后一次都不被发现。
A若一开始小偷在*左侧，则一开始的距离为0，当*连续搜查两次n-1号，距离变为奇数，这时小偷既不能从左侧逃到右侧，又在*搜到3号时与*的距离为奇数，则小偷必在1号房间，则下次*搜查2号时，必然会被发现；
B若一开始小偷在*右侧，且距离为奇数，即没有从右侧越到左侧的机会，则在*搜索n-2时，必然在n号房间，则在*搜索n-1号时必然会被发现；
C若一开始小偷在*右侧，且距离为偶数，此时分两种情况讨论
i若小偷没有逃到左侧，则*第一次搜查n-1时，必然在n，则*第二次搜查n-1时必然发现之；
ii若小偷逃到了左侧，即不能再次逃到右侧；在*两次搜查完n-1后，距离变为奇数，最终会在2号房间被发现。
综上，n个房间时，最多用时2(n-2)
