1

选择a：移动 a[i] 个小区

2

选择b：移动b[i] 个小区

•  当没有合法的选择序列时，输出 “No solution!”。

• 当字典序最小的字符串无限长时，输出 “Infinity!”。

• 否则，输出这个选择字符串。

• 存在整数 i ≥ -1，使得∀j，0 ≤ j ≤ i，满足s[j]  = t[j] 且 s[i+1] < t[i+1]。

• 其中，空字符 < ‘a’ < ‘b’。

用例名称

7个小区的范围

输入

7

5 -3  6 5 -5 -1 6

-6 1  4 -2 0 -2 0

分析步骤

假设快递员T，小区列表Z，其移动步骤如下：

1. 数列a={5,-3,6,5,-5,-1,6} 数列b={-6,1,4,-2,0,-2,0}

2. 开始时，T在小区Z[0]的位置，其中a[0]=5，b[0]=-6，假设选择a[0]=5向前移动5个小区，该移动是在合法的范围内；假设选择b[0]=-6，则向后移动6个小区，因为T当前的位置在第一个小区Z[0]，所以该移动不在合法的范围内，所以该步骤选择a[0]=5,输出的字符是a

3.  第2步骤a[0]=5已向前移动5个小区，当前T位于a[5]=-1的第5号个小区的位置，其中b[5]=-2，假设选择b[5]=-2，则T向后移动2一个第3号小区到b[3]=-2，再向后移动2个小区到第1号小区b[1]=1，再向前移动1个小区到第2号小区b[2]=4，刚好a[2]=6，则T可选择直达第6号小区a[2]，则该路线的输出字符串是abbba

4. 第2步骤a[0]=5已向前移动5个小区，当前T位于a[5]=-1的第5号个小区的位置，其中b[5]=-2，假设选择a[5]=-1，向后移动1个小区到第4号小区a[4]=-5，刚好b[4]=0，此时如果T选择a[4]则向后移动5个小区不在合法的范围内，此时如果选择b[4]=0则在原地踏步不在合法的范围内，所以该路线没有合法的输出

5.  最终确定的路线是abbba

输出

最小的字符串是abbba

主流程算法逻辑

1. 在每一个步骤的选择中，优先选择按照a[i]数列的方式移动，a的字符小于b字符的字典排序

2. 假设k+a[k]=i，在按照a[i]数列的方式移动中出现不合法的范围，此时i+a[i]在不合法范围，则按照b[i]方式移动

3.  在第2步骤中按照b[i]的方式移动出现不合法的范围，则回退到第2步骤按照b[k]方式移动，

4. 在第2步骤中按照b[i]的方式移动范围合法，则执行第2步骤又按照a[i+b[i]]的方式移动

5.  在以上的执行的步骤中，如果出现超出数组索引范围的移动，则回退到上一移动点

6.  在以上的执行步骤中，如果出0位移动或者回到原点移动，则不存在合法路径，退出

7. 在以上的执行步骤中，如果到达终点，则输出最小路径的字符串，退出

名称

a[i]数列与b[i]数列

类型

一维数组

长度

随机长度

描述

存储可供选择的路径的小区以及路径的移动方式，索引表示小区的编号，数组元素表示路径的移动方式

名称

存储路径

类型

二维数组

长度

可变长，根据路径的长度而定

描述

第一维度表示路径中的每个小区

第二维度表示a[i]或者b[i]中的元素，索引0表示类型，其中1表示a[i]、2表示b[i]，索引1表示a[i]或b[i]的索引

主流程

• 持续查找合法的路径，其中优先选择a[i]中的小区

• 非法路径则回退到上一步的小区变换方向继续查找

条件判断

• 合法路径则继续

• 非法路径则回退  

• 重复路径则退出

• 到达终点则完成

用例描述

随机生成7个小区

执行次数：100

输入数列：随机数列

输出数：最小字符串

覆盖函数：所有函数

用例描述

随机生成100个小区

执行次数：100

输入数列：随机数列

输出数：最小字符串

覆盖函数：所有函数

输入数列长度

输出数列长度

耗时

1024*1024

20毫秒

1024*1024*2

30毫秒