信息
- ID
- 81
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
我们很容易得到一个贪心的算法:把最小的 A 和最大的 B 配对,第二小的 A 和第二大的 B 配对 ...... 最大的 A 和最小的 B 配对。
这事实上是一个插入排序,每次 O(n) 判断,最终复杂度 O(n2)
注意到所有 A 和 B 不超过100。
利用这个条件,我们维护列表 totA:totA[i] 表示大小为 i 的 A 有多少个
同理定义 totB
这样在得到新的 A,B 时,我们可以 O(1) 的将其插入。
在回答询问时,我们只需维护两个指针 p 和 q,设 totA[p] 和 totB[q] 的较小者为 T,将两者都减去 T,得到 T 对 (totA[p],totB[q]),然后继续移动两个指针即可。
时间复杂度 O(100n)。