Various Kagamimochi

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$.

You choose two mochi out of the $N$ mochi, and place one on top of the other to form one kagamimochi.

Find how many different kinds of kagamimochi can be made.

Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

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$ $\cdots$ $A_N$

Output

Print the number of different kinds of kagamimochi that can be made.

Solving

二分法（利用lower_bound二分）：

 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


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
const int N = 0;
int t;    
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> A(n+1);
    for(int i=1;i<=n;i++) cin >> A[i];
    auto countKagamimochi = [&]()
    {
    long long count = 0;
    int N = n;
    for (int i = 1; i <= N; ++i)
    {
        auto it = lower_bound(A.begin() + i + 1, A.end(), 2 * A[i]);//查找第i个mochi之后第一个大于等于2*A[i]的元素的位置，并返回迭代器。
        if (it != A.end()) 
        {
            count += A.end() - it;//该元素之后的所有元素都可以与其组成Kagamimochi
        }
    }
    return count;
};
    cout << countKagamimochi();
    return 0;
}

双指针：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


#include <bits/stdc++.h>
using namespace std;
const int Maxn = 5e5 + 10;
int a[Maxn];
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++) cin >> a[i];
    int l = 1,r = 1;
    int ans = 0;
    while(l <= n)
    {
        while( r <= n && a[r] < a[l] * 2 ) r++; 
        ans += n - r + 1;
        l++;
    }
    cout << ans;
    return 0;
}