【题解】CF1393C Pinkie Pie Eats Patty-cakes

题目

CF1393C Pinkie Pie Eats Patty-cakes

题解

题目即求任意两个相同数的距离的最小值的最大值,可以二分答案。在判断距离>=d是否可行时,用贪心思想:依次填写数列中的数,每次填写时,填重复次数最多的且符合条件的数。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月18日 下午4:38

【小白解析】
此题的解题思路遵照生活常识:排列一串含多组相同数字的数列时,尽可能先安放出现次数多的数字。此题二分的判断意义便在此。
第10行将所有出现过的数字推入优先队列中;队列与pair类的性质决定了cnt[i]——即出现次数最大的数字被优先排列在队列前端。
12行开始的for循环中,i不再表示数字(馅饼类型)本身,而是表示数列tmp的第i位;14行i-d-1的实际意义为“与第i个数字相隔正好d位之处”,而tmp[i-d-1]则表示该处的数字,对应的cnt表示该数字的出现次数;若出现次数不为0,因为该数字与上一个相同的数字正好隔开d个数字,故可以允许该数字再加入队列一次。
16行考察当前优先队列中(未加入数列的数字中)出现次数最多的数字,将其弹出优先队列并安插在tmp的i处。
回到第15行;当优先队列为空时,说明上一步(14行)没有操作成功,即对于数字tmp[i],无法保证它与相同的数字间隔d格以上(即tmp[i-d-1]存在);或是优先队列中一开始就没有超过d个不同的数字,故不成立,向左查询d范围。
若能成功遍历完n个数字,说明d仍有扩充的余地,向右查询。
*话说复制c[]的必要性是啥?