首页 > 爱奇艺算法第二题
头像
offer快来砸我!!
编辑于 2020-09-13 17:02
+ 关注

爱奇艺算法第二题

爱奇艺算法第二题,求大佬指教
题目描述:
小i君喜欢帮助别人解决问题,但是,今天它遇到了一个无法解决的问题,需要你来帮助它:

小i君有n组由小写英文字母组成的字符串序列,他希望按字典顺序对它们进行排序(如字典中的排序),对于字符串序列中的每个字符串,但是它不能交换字符串中的任何一个字符,它被允许做的唯一操作就是反转字符串(例如:第一个字符变为最后一个字符,第二个字符变为倒数第二个字符,依此类推)。

为了反转第i个字符串,小i君必须消耗Ci能量单位,它希望消耗最小的能量来排序字符串序列。

以下两种情况,在字典序中,A字符串小于B字符串

(1)如果字符串A短于字符串B(|A|<|B|)并且A是B的前缀

(2)它们互相不为前缀,但是在第一个字符位置,A的字符小于B的字符。

注意:字符串中两个相等的字符不会破坏按字典顺序排序的条件。



输入描述
输入的第一行包含一个整数n(2≤n≤100 000),代表字符串序列有多少组字符串。

第二行包含n个整数Ci(0≤Ci≤10^9),第i个整数等于小i君为了反转第i个字符串而必须花费的能量。

然后跟随n行,每行包含一个由小写英文字母组成的字符串。 这些字符串的总长度不超过100 000。

输出描述
如果无法反转某些字符串以使它们按字典顺序排列,请打印-1;

否则,请打印消耗的最少总能量。

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐