111qqz的小窝

老年咸鱼冲锋!

hdu 6034 2017 Multi-University Training Contest – Team 1 B Balala Power! (贪心)

http://acm.hdu.edu.cn/showproblem.php?pid=6034

题意:

有一个仅由小写字母组成的字符串,要求将a..z的字母,对应到0..25,每个数字只能被一个字母对应,得到一个26进制的数,现在问这个数最大是多少。注意不允许有前导0,除非这个数本身就是0.

 

思路:

贪心。看哪个字母的权值最大。

可以用类似高精度加法的方式处理。

对于前导0的部分,用一个bool标记首位(如果字符串长度为1就不标记)

对于26个高精度数的排序,可以用交换id的技巧。

以及,如果排序之后,发现权值最小的数被对应到数字0,但是又在某个长度大于1的字符串的首字母位置出现过。

我初始想当然得,把该字母和最小的可以出现在首位的字母交换….

然而这很错啊?

实际上,更优秀做法是,找到第一个可以出现在首位的字母,然后从该字母后面到结尾,依次前移一位,最后把这个可以出现在首位的字母放在最后。

比如这组数据:

7
abcdefghijklmnopqrstuvwxyz
zz
yy
xx
ww
uu
vv

 

权值按照从大到小排列

z u v w x y t 显然不如  u v w x y z t  优

 

 

 

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz