考虑采用双指针法解决此题。
首先需要对 \(a,b\) 数组排序,并且维护两个指针 \(l,r\),分别指向 \(a,b\) 两个数组中的元素。
接着循环移动 \(r\) 指针,每次都尝试匹配 \(a_l\) 和 \(b_r\):
-
若 \(a_l \le b_r\),则说明 \(a_l = b_r\) 或可以采用减少 \(b_r\) 的方式使 \(a_l = b_r\),这时我们就称 \(a_l\) 和 \(b_r\) 匹配成功。接着令不需要添加的元素个数 \(ans \gets ans+1\),同时也令 \(l \gets l+1\)(右移一位)。
-
否则,则说明需要添加一个元素,不进行任何操作。
当 \(l,r\) 指针移动到末尾时循环结束,此时的答案即为 \(n-ans\)。
代码非常好写,因此不贴了。
标签:题解,CF387B,Round,ans,gets,George,指针 From: https://www.cnblogs.com/XOF-0-0/p/18062506