Readme

2576.Find-the-Maximum-Number-of-Marked-Indices

一个比较容易想到的贪心策略就是，对于最小的元素a，我们找到对应的恰好满足b>=2a的元素b与之配对。目的是尽量保留更大的元素可以用来匹配次小的元素。然后重复这样的过程。

但是这种策略会遇到这样的一个例子：[2,4,5,9]。当2与4匹配之后，此时未被匹配的次小元素是5，反而变得更大了。

正确的思考方式是：如果总元素是n，那么最多能匹配n/2对。为了更多地凑出这些pairs，每个pair的较小值必然在排序后的nums的前半部分，而较大值在nums的后半部分。假设有一对[a,b]都在前半部分，另一对[c,d]都在后半部分，那么必然可以重构出两对[a,c],[b,d]同样更容易条件。同理，可以证明出其他情况下，任何处于同一个半区的配对都不会是最优解。

所以本题只需要使用双指针，第一个指针i在前半区遍历，第二个指针j在后半区遍历，对于每个i单调移动j看看是否能有配对即可。

本题在codeforces上的原题是：https://codeforces.com/contest/372/problem/A