Source and Judge
Record
1h
Analysis
一开始看错题意了,决策可以是动态的,根据取出来的数再决定下一步
如果是静态的话,显然最多搞两个集合
考虑枚举每一种颜色
一、如果某个集合有多个,贡献为 len-其他种类+2(取光其他所有才出来)
二、分开来, len-其他种类+1 最少的两个之和(最后才出来)
时间复杂度n
其实改成动态并不难,最多搞两个集合这个性质依然是对的,但不能再枚举具体颜色了
一、如果某个集合有多个,贡献为 颜色种类+1
二、分开来
这里是难点
自己曾想到一种情况,但不知道怎么解决:
可能我后面取出来的答案即使加上取出来的消耗依然比早出来的小
然后看到动态决策就很蒙蔽,不知道怎么处理……
其实很容易证明,最坏情况一定是按贡献从大到小出来的
用微扰可以证明,其他的情况都会比这个更优
所以排序后每个的贡献就很明确了,即「存在此颜色的所有集合中,除了这个之外,最小的 其他颜色个数+1」
(这里我们不再考虑,因为取到别的相同颜色而停止的情况,因为在前面已经计算过了)
1 | //Zory-2018 |