一条通道上怎样选择总步数最少的集合点:九组角色的二十一个候选集合点·案例25
让一个位置尽量远离别人,与让所有角色走到某处的总路程最小,是不同目标。若角色沿同一条通道移动,且每个位置有不同人数,可以逐点计算总步数来找到集合点。
以下是一组可按记录复查的虚构游戏例子。它先固定输入、单位和执行顺序,再展示每一步结果。读者可以用纸笔挑出几步核对,不需要依赖具体游戏的后台数据。
明确规则与输入
九组角色各有整数位置与人数,位置在零到二十内。候选集合点是同一区间的每个整数;成本等于各组人数乘到集合点的绝对距离之和。取最低成本,同分选择更靠左的位置。
九组[位置,人数][[16, 1], [8, 5], [12, 5], [2, 5], [6, 4], [16, 5], [2, 3], [1, 5], [16, 3]]
完整计算过程
集合点0:九组分别需要步数[16, 40, 60, 10, 24, 80, 6, 5, 48],合计289;该数字是人数加权的总步数,不是最远一人的距离。
集合点1:九组分别需要步数[15, 35, 55, 5, 20, 75, 3, 0, 45],合计253;该数字是人数加权的总步数,不是最远一人的距离。
集合点2:九组分别需要步数[14, 30, 50, 0, 16, 70, 0, 5, 42],合计227;该数字是人数加权的总步数,不是最远一人的距离。
集合点3:九组分别需要步数[13, 25, 45, 5, 12, 65, 3, 10, 39],合计217;该数字是人数加权的总步数,不是最远一人的距离。
集合点4:九组分别需要步数[12, 20, 40, 10, 8, 60, 6, 15, 36],合计207;该数字是人数加权的总步数,不是最远一人的距离。
集合点5:九组分别需要步数[11, 15, 35, 15, 4, 55, 9, 20, 33],合计197;该数字是人数加权的总步数,不是最远一人的距离。
集合点6:九组分别需要步数[10, 10, 30, 20, 0, 50, 12, 25, 30],合计187;该数字是人数加权的总步数,不是最远一人的距离。
集合点7:九组分别需要步数[9, 5, 25, 25, 4, 45, 15, 30, 27],合计185;该数字是人数加权的总步数,不是最远一人的距离。
集合点8:九组分别需要步数[8, 0, 20, 30, 8, 40, 18, 35, 24],合计183;该数字是人数加权的总步数,不是最远一人的距离。
集合点9:九组分别需要步数[7, 5, 15, 35, 12, 35, 21, 40, 21],合计191;该数字是人数加权的总步数,不是最远一人的距离。
集合点10:九组分别需要步数[6, 10, 10, 40, 16, 30, 24, 45, 18],合计199;该数字是人数加权的总步数,不是最远一人的距离。
集合点11:九组分别需要步数[5, 15, 5, 45, 20, 25, 27, 50, 15],合计207;该数字是人数加权的总步数,不是最远一人的距离。
集合点12:九组分别需要步数[4, 20, 0, 50, 24, 20, 30, 55, 12],合计215;该数字是人数加权的总步数,不是最远一人的距离。
集合点13:九组分别需要步数[3, 25, 5, 55, 28, 15, 33, 60, 9],合计233;该数字是人数加权的总步数,不是最远一人的距离。
集合点14:九组分别需要步数[2, 30, 10, 60, 32, 10, 36, 65, 6],合计251;该数字是人数加权的总步数,不是最远一人的距离。
集合点15:九组分别需要步数[1, 35, 15, 65, 36, 5, 39, 70, 3],合计269;该数字是人数加权的总步数,不是最远一人的距离。
集合点16:九组分别需要步数[0, 40, 20, 70, 40, 0, 42, 75, 0],合计287;该数字是人数加权的总步数,不是最远一人的距离。
集合点17:九组分别需要步数[1, 45, 25, 75, 44, 5, 45, 80, 3],合计323;该数字是人数加权的总步数,不是最远一人的距离。
集合点18:九组分别需要步数[2, 50, 30, 80, 48, 10, 48, 85, 6],合计359;该数字是人数加权的总步数,不是最远一人的距离。
集合点19:九组分别需要步数[3, 55, 35, 85, 52, 15, 51, 90, 9],合计395;该数字是人数加权的总步数,不是最远一人的距离。
集合点20:九组分别需要步数[4, 60, 40, 90, 56, 20, 54, 95, 12],合计431;该数字是人数加权的总步数,不是最远一人的距离。
最低总步数183,按同分靠左规则选8;全部最低点[8]。
独立核对与边界
可以不用逐个候选求全部距离:从最左候选开始,每右移一步,左侧及当前位置人数多走一步,右侧人数少走一步,成本差等于两边人数之差。用这条差分记录独立核对全部候选成本。
这里的成本按通道距离相加,没有障碍、拥挤、限速或不同角色的移动能力。人数作为权重不能误写成位置编号。最低点可能不唯一,靠左只是一条稳定的同分规则,并不表示其他最低点错误。
练习时只改变一个条件,先判断哪些中间步骤应当受影响,再重新计算。要把空状态、数值零和未能确定的结果分开。边界约定不同可能产生不同答案,复查的目标是确认输入、过程与规则一致,而不是只追求最后一个数字看起来相同。
