Problem Statement

There are $N$ mochi (rice cakes), arranged in ascending order of size. The size of the $i$-th mochi $(1\leq i\leq N)$ is $A_i$.

Given two mochi $A$ and $B$, with sizes $a$ and $b$ respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi $A$ on top of mochi $B$ if and only if $a$ is at most half of $b$.

Find how many kagamimochi can be made simultaneously.

More precisely, find the maximum non-negative integer $K$ for which the following is possible:

• From the $N$ mochi, choose $2K$ of them to form $K$ pairs. For each pair, place one mochi on top of the other, to make $K$ kagamimochi.

Constraints

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
• $A_i \leq A_{i+1} \ (1 \leq i < N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $A_1$ $A_2$ $\dotsc$ $A_N$

Output

Print the maximum $K$ such that $K$ kagamimochi can be made simultaneously.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
using namespace std;
const int Maxn = 5e5 + 10;
int a[Maxn];
int n;
bool check(int x)
{
    for(int i=1;i<=x;i++)
    {
        if(a[i]*2 >a[n-x+i])return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    int l = 0,r = n/2,mid;
    while(l+1!=r)
    {
        mid = (l+r)>>1;
        if(!check(mid)) r = mid;
        else l = mid;
    }
    //由于不是l<r的二分形式，所以还要在l和r之间选择答案 
    //以l+1!=r的形式二分可以清晰的输入边界条件（均为mid），仅需多加此判断条件.
    if(check(r))
    {
        l = r;
    }
    cout << l;
    return 0;
}

使用 while(l + 1!= r) 形式的二分查找时，通常确实需要额外添加一步判断来确定最终答案。

这种二分查找写法在循环结束后，只是把答案范围缩小到了两个相邻的值，即 l 和 r，但并没有明确指出哪个值才是真正满足条件的结果。因此，为了得到准确答案，需要依据具体的判定条件（例如本题中的 check 函数），对 l 和 r 分别或其中之一进行再次验证。

不过，要是能确定在循环结束时，其中某个指针必然指向正确结果，那就无需额外判断。但多数情况下，很难提前做出这样的保证，所以添加额外判断是一种稳妥、通用的做法，能确保代码逻辑的正确性。