求助大佬,第三个测试点一直过不了。
  • 板块P1102 A-B 数对
  • 楼主mosili
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/10 21:20
  • 上次更新2024/11/11 09:19:37
查看原帖
求助大佬,第三个测试点一直过不了。
1006108
mosili楼主2024/11/10 21:20
//二分查找
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2000010;
typedef long long LL;
long long q[N];

//返回对应数值在数组中出现的次数
int half_find(LL q[], int n, LL m)
{
	int l = 0, r = n - 1, l_0, r_0;
	while (l < r)
	{
		int mid = (l + r + 1) / 2;
		if (q[mid] <= m) l = mid;
		else r = mid - 1;
	}
	if (q[l] != m) return 0;
	else
	{
		r_0 = r;
		l = 0;
		r = n - 1;
		while (l < r)
		{
			int mid = (l + r) / 2;
			if (q[mid] >= m) r = mid;
			else l = mid + 1;
		}
		l_0 = l;
		return r_0 - l_0 + 1;
	}
}

int main()
{
	int res = 0;
	int n, m;//输入总字符数量,以及你所想查找的字符
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> q[i];
	sort(q, q + n);
	for (int i = 0; i+1 < n; i++)
	{
		LL target = q[i] + m;
		res += half_find(q+i+1, n-i-1, target);
	}
	cout << res;
	return 0;
}


2024/11/10 21:20
加载中...