请教一下D的这个思路有什么问题

首先数字的插入顺序不影响结果,假设某个数x是最先插入的,$x_i$表示x从高到低第i位。

后面的数字插入时,如果$x_2 \ge x_1$,那么把新的一部分数字插入$x_2$与$x_1$之间肯定不如插在$x_1$左边或插在$x_2$右边更优,也就是说在最终的串里$x_1$跟$x_2$一定是相邻的。$x_3 \ge x_1$时根据数学归纳法同理,直到遇到第一个$x_i<x_1$。那么可以知道$x_1\cdots x_{i-1}$在最终的串里一定是连续的。然后把$x_i$作为新的$x_1$继续处理,这样就能把一个数字拆分成若干个在最后一定连续的子串。(因为有$x_i < x_1$,所以同一个数字拆出来的字串排序后相对顺序不会变)

这样就变成了经典的对于若干字符串,把它们首位相连后字典序最大是多少。把这些字符串排序,比较大小时用最低位补齐到一样的长度来比较(比如27跟275比较时,把27用最低位7补齐到277,然后277跟275进行比较277>275,所以27排在275前面)排序后从大到小输出字符串就是结果。

全部评论

相关推荐

02-24 10:34
门头沟学院 Java
已注销:之前发最美的女孩基本爱答不理,发最帅的hr终于有反馈了,女孩子也要自信起来
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务