【学习笔记】NOIP模拟赛

给国的锟题 (problem)

• 数据结构神题猜的
• 首先分析性质，如果某次时刻剩下来某道题，那么后面不论怎么添加这道题都会剩下来
• 考虑维护每个人选了哪些题，初始每个人拿着的都是$a[i]$
• 考虑一个巧妙的转化，每次新加入一道题，然后依次考虑每个人是否拿自己手中的题进行交换
• 部分分到手
• 对于一段连续的$0$只会弹出最大的那个元素，对于一段连续的$1$只会弹出最小的那个元素
• 如果相邻的两个堆满足$max[i]\le min[i+1]$，那么我们可以交换两个堆的位置。我们只需要说明任何$v$经过两个堆过后弹出的元素相同并且$max[i]\ge min[i+1]$。后者是显然的。前者也是显然的
• 那么现在我们可以合并了。
• 考虑分析复杂度。如果满足$max[i]>min[i+1]$那么一定会发生变化
• 设当前有$L$对堆。重叠部分$\sum \varphi (i)=k$，那么根据鸽巢原理在期望状态下经过$\frac{2k}{L}$轮后至少有一半$\varphi (i)$变成$0$，那么就会有一半的堆被合并掉
• 复杂度$O(k{\log }^{2}k)$
• AC Code