社区讨论

一个贪心的思路

P14954520参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mjzqj1ag
此快照首次捕获于
2026/01/04 20:55
2 个月前
此快照最后确认于
2026/01/05 12:42
上个月
查看原帖
麻烦在只有1个字符匹配的情况,假设按照字符 002255的顺序贪心,补的次数分别是 tabt_{ab}tact_{ac}tbct_{bc},有可能 tabt_{ab} 过多导致处理最后一个字符时 bb 不够,结果并不能保证最优。
题解里基本都是用循环不断贪心解决,也可以在处理最后一个字符时允许一次反悔,把 tabt_{ab} 适当匀一些给 tact_{ac},在前两个字符总结果不变的情况下使剩下的 bbcc 尽可能均匀分布,就能保证结果最优了。题解发不了了,就发讨论版吧 ^_^

回复

2 条回复,欢迎继续交流。

正在加载回复...