#2 ,#3TLE
  • 板块P1102 A-B 数对
  • 楼主_NOCl_
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/3 13:11
  • 上次更新2023/11/2 16:20:16
查看原帖
#2 ,#3TLE
1054699
_NOCl_楼主2023/10/3 13:11

#2 ,#3寄了 求助 主要是不想调用 upperbound和lowerbound

#include<iostream>
#include<algorithm>
using namespace std;

long long lowLoc(long long* arr, long long size, long long p) {
	long long l = 0, r = size - 1,result=-1;
	long long mid;
	while (l <= r) {
		mid = l + (r - l) / 2;
		if (arr[mid] < p)l = mid + 1;
		else if (arr[mid] > p) r = mid-1;
		else { r--; result = mid; }
	}
	return result;
}
long long highLoc(long long* arr, long long size, long long p) {
	long long l = 0, r = size - 1, result = -1;
	long long mid;
	while (l < r) {
		mid = l + (r - l) / 2;
		if (arr[mid] == p)result = mid;
		if (arr[mid] > p) r = mid;
		else l = mid + 1;
	}
	if (result!= -1)result = result + 1;
	return result;
}
int main(){
	long long N, C, ans=0;
	cin >> N >> C;
	long long* a = new long long[N];
	for (int i = 0; i < N; i++) cin>>a[i];

	sort(a, a + N);
	for (long long i = 0; i < N; i++)
	{
 		ans =ans + (highLoc(a, N, a[i]-C)-lowLoc(a, N, a[i]-C));
	}
	cout << ans;
	return 0;
}
2023/10/3 13:11
加载中...