做法一、反悔贪心

感觉直接贪会出现一些奇怪的 bug，所以采用反悔贪心。
具体地说开两个小根堆，一个是二元组存当前决策（大的那个做第一关键字升序），另一个是当前未决策的数。
然后贪贪贪贪贪，悔悔悔悔悔。
$O(n \log n)$。

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 5e5 + 15;
int n, a[N];

priority_queue< PII, vector<PII>, greater<PII> > q1;
priority_queue< int, vector<int>, greater<int> > q2;
int ans = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        if (q2.size() && q2.top() * 2 <= a[i]) { q1.push({a[i], q2.top()}), q2.pop(); ans++; continue; }
        if (!q1.size()) { q2.push(a[i]); continue; }
        int x = q1.top().second, y = q1.top().first; q1.pop();
        q2.push(y), q1.push({a[i], x});
    }
    printf("%d\n", ans);    
    return 0;
}

做法二、二分

好像很神奇啊。二分答案，然后一定取前 $mid$ 个数最优，接下来直接在 check 内 lowerbound 就做完了。
复杂度 $O(n \log^2 n)$，更劣但好写好调。

做法三、双指针

基于做法二，且答案不超过 $\lfloor \frac{n}{2} \rfloor$，所以对前 $\lfloor \frac{n}{2} \rfloor$ 个数和后面剩余的数双指针。
事实证明直接贪就是对的。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 15;
int n, a[N], ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int now = n / 2 + 1;
    for (int i = 1; i <= n / 2; i++) {
        while (a[i] * 2 > a[now] && now <= n) now++;
        if (now > n) break;
        ans++, now++;
    }
    printf("%d\n", ans);
    return 0;
}