请教一下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前面)排序后从大到小输出字符串就是结果。

全部评论

相关推荐

千千倩倩:简历问题有点多,加v细聊
点赞 评论 收藏
分享
09-29 16:59
已编辑
门头沟学院 Java
牛客96609213...:疯狂背刺,之前还明确设置截止日期,还有笔试,现在一帮人卡在复筛,他反而一边开启扩招,还给扩招的免笔试,真服了,你好歹先把复筛中的给处理了再说
投递大疆等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务