求助,写的二分t了
  • 板块P1102 A-B 数对
  • 楼主hopper_
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/12/18 15:39
  • 上次更新2024/12/18 20:16:46
查看原帖
求助,写的二分t了
190384
hopper_楼主2024/12/18 15:39
#include <bits/stdc++.h>
#define int long long
using namespace std;

//求上界
int up_bound(int l,int r,int x,vector<int> vec){
	while(l < r){
		int mid = (l + r + 1) >> 1;
		if(vec[mid]<=x){
			l = mid;
		}else{
			r = mid - 1;
		}
	}
	if(vec[l]==x) return l + 1;
	else return -1;
}

//求下界
int down_bound(int l,int r,int x,vector<int> vec){
	while(l < r){
		int mid = (l + r) >> 1;
		if(vec[mid]>=x){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	if(vec[l]==x) return l + 1;
	else return -1;
}

signed main(){
	int N,C;
	cin >> N >> C;
	vector<int> vec;
	for(int i=0;i<N;i++){
		int x;
		cin >> x;
		vec.push_back(x);
	}
	sort(vec.begin(),vec.end());
	int ans = 0;
	for(int i=0;i<N;i++){
		int tmp = vec[i] + C;
		if(down_bound(0,N,tmp,vec)!=-1){
			ans += up_bound(-1,N-1,tmp,vec) - down_bound(0,N,tmp,vec) + 1;
		}
	}
	cout << ans << endl;
	return 0;
}
2024/12/18 15:39
加载中...