uva 10785 The Mad Numerologist

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1726
题意:给出26个大写字母的权值,要求构造一个长度为n(n不超过210)的字符串。并且满足奇数位置只能放元音字母,偶数位置只能放辅音字母,且每个元音字母最多放21次,每个辅音字母最多放5次,要求构造的字符串的权值之和最小,在权值最小的前提下字典序最小。

思路:贪心。一开始错误得以为不是完整得不能交换(也就是不完整的字母只能放在最后,这是错误的)。但实际上只要每个字母的数量不变,那么就不影响权值。所以做法是,奇数位置偶数位置分别搞,先把构成字符串的字母按次存入,然后排序一下,输出即可。

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz