qw Round -1 Solution

NaOH_Frog · 2023-07-23 10:32:45 · 个人记录

A

将五项指标得分加起来，判断总分在哪个颜色区间内即可。

B

按照题意模拟即可，题面等价于让你求出最大的 l 和最小的 r 使得 l 左边和 r 右边都没有 1。复杂度 O(n)。

C

按照题意模拟即可。注意按照队列中顺序输出上场的两人，手写队列维护队列情况并用 map 维护每个人的位置（或者是否在队列中）。复杂度 O(n\log n)。

D

发现每个人的快乐值关于 k 单调不降，考虑二分答案。

检查某个 k 是否合法，可以通过类似双指针的方法维护与当前位置 i 差小于等于 k 的关键点（即包含于 b 中的点）有几个在 i 左边，有几个在 i 右边，动态修改答案即可，具体细节可以参考代码。复杂度 O(n)。

二分次数复杂度为 O(\log a_i)，总复杂度为 O(n\log a_i)。注意答案上界并不是 \max a_i，但是数据只卡了 10 分（m=1 的部分分）。