AT_abc388_c [ABC388C] Various Kagamimochi

题目

有

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 见祖宗。

CPP

#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;
}

AT_abc388_c [ABC388C] Various Kagamimochi

文章操作

题目

思路

代码

相关推荐

评论

AT_abc388_c [ABC388C] Various Kagamimochi