#P18568. [ukiepc2026]Hoptimisation
[ukiepc2026]Hoptimisation
Hoptimisation
题目描述
有一排连续排列的 个格子,物理位置从左到右编号为 ,相邻两个格子的距离为 米。
每个格子都要分配一个互不相同的名字。现在给定一份依次访问的格子名字列表 。假设名字 被分配到位置 ,则按照列表依次跳跃所需的总距离为
你可以决定每个名字应当放置在什么位置。如果输入中出现的不同名字少于 个,可以自行为未使用的格子添加其他合法、互不相同的名字。
请输出一种使总跳跃距离最小的格子命名排列。
图示(重绘示意图)

图 H.1:样例 1 中跳格名称的排列与连续访问产生的跳跃距离。 本图为重绘示意图。
输入格式
第一行输入两个整数 ,分别表示格子数和访问列表长度。
第二行输入 个仅由小写英文字母组成的非空字符串 ,表示依次访问的格子名字。
输出格式
输出 个字符串,从左到右依次表示位置 到 的格子名字。
输出的名字均应为长度不超过 的小写英文字母串,且彼此不同。所有在输入中出现过的名字都必须出现恰好一次。
若存在多种最优方案,输出任意一种即可。
样例 #1
输入
5 4
hop skip hop jump
输出(答案不唯一)
anything jump hop skip something
样例 #2
输入
9 16
a b c a b c a x y z x y z e f g
输出(答案不唯一)
g f e z y x a c b
数据范围与保证
- ;
- ;
- 所有输入名字均由小写英文字母组成,长度为 到 ;
- 输入中不同名字的数量不超过 。