ARC120D题解

迟暮天复明 · 2023-10-30 19:35:06 · 题解

首先楼上已经证明过一定是较小的 n 个数与较大的 n 个数匹配。

然后对原数组从左到右扫一遍，如果遇到的数是较小的 n 个数之中的，那么将其放入第一个队列中。否则放入第二个队列中。

如果两个队列的元素个数均不为零，则将队首进行匹配。

证明：如果我匹配的数字是 i 和 j，那么 i 到 j 之间的数一定不可能与 i 之前的数匹配（否则为什么不和 i 匹配），同时 i 到 j 之间的数都一定已经匹配过了（否则 i 和 j 至少有一个不是队首）。由于已知左右括号数均为 n 个，故得证。

时间复杂度还是 O(n\log n)，因为要排序。