二分边界,有三个点过不了
  • 板块P1102 A-B 数对
  • 楼主saruo233
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/20 18:21
  • 上次更新2024/3/20 20:40:18
查看原帖
二分边界,有三个点过不了
1180817
saruo233楼主2024/3/20 18:21
#include <iostream>
#include <algorithm>
int Array[200005];
int N, C, l, r, mid;
int ans = 0;
int LB, RB;
void FindB1(int l, int r, int B)
{
	while (l <= r)
	{
		mid = l + ((r - l) / 2);
		if (Array[mid] >= B)
			r = mid - 1;
		else
			l = mid + 1;
	}
	if (Array[++r] == B)
		LB = r;
	else
		LB = -1;
}
void FindB2(int l, int r, int B)
{
	while (l <= r)
	{
		mid = l + ((r - l) / 2);
		if (Array[mid] > B)
			r = mid - 1;
		else
			l = mid + 1;
	}
	if (Array[--l] == B)
		RB = l;
	else
		RB = -2;
}
int main(void)
{
	std::cin >> N >> C;
	for (int i = 0; i < N; i++)
	{
		std::cin >> Array[i];
	}
	std::sort(Array, Array + N);
	int B;
	for (int i = 0; i < N; i++)
	{
		B = Array[i] - C;
		if (Array[1] > B)
			continue;
		FindB1(0, N - 1, B);
		FindB2(0, N - 1, B);
		ans += RB - LB + 1;
	}
	std::cout << ans;
	return 0; 
}
2024/3/20 18:21
加载中...