AT_abc388_c [ABC388C] Various Kagamimochi

· · 题解

洛谷链接

AtCoder链接

题目

有 N 个年糕，按大小升序排列。第 i 个年糕的大小是 A_i \ (1 \le i \le N)。

给定大小分别为 a 和 b 的两个年糕 A 和 B，当且仅当 a 小于等于 b 的一半时，你可以将年糕 A 放在年糕 B 的上面，制作一个叠年糕。

你从 N 个年糕中选择两个年糕，并将一个放在另一个上面，组成一个叠年糕。求可以做出多少种不同的叠年糕。

思路

由于 2 \le N \le 5 \times 10^5，很明显直接遍历所有年糕会超时。

既然直接求解不好求，那么我们就换一种思路。我们先选定一个年糕作为叠年糕中上面的年糕，设它的大小为 a。因为 A_i \le A_{i+1}，所以不难想出如果第 i 个年糕的大小满足 a \le \dfrac{A_i}{2}（即可以作为叠年糕中下面的年糕），那么在这个年糕后面的年糕的大小也一定满足，我们就没有必要去判断了。

这样，我们只要求出第一个符合要求的年糕的下标，从而求出符合要求的年糕的数量即可。

这里，我用 C++ 自带的 lower_bound 函数（不会用的可自行上网查询）去二分查找这个下标。

代码

十年 OI 一场空，不开 long long 见祖宗。

#include <bits/stdc++.h>

using namespace std;

long long n, a[500010], res, pos;

int main()
{
    scanf("%lld", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%lld", &a[i]);
    for (int i = 0; i < n; i ++ )
    {
        pos = lower_bound(a, a + n, a[i] * 2) - a;
        res += n - pos;
    }
    cout << res << '\n';
    return 0;
}