二分RE??
  • 板块P1102 A-B 数对
  • 楼主spessert
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/5/2 16:48
  • 上次更新2024/5/2 19:42:40
查看原帖
二分RE??
881317
spessert楼主2024/5/2 16:48
#include<bits/stdc++.h>
using namespace std;
int num[30000];
int main(){
	int n,C;
	cin>>n>>C;
	for(int i=1;i<=n;i++){
		cin>>num[i];
	}
	long long cnt=0;
	sort(num+1,num+n+1);
	for(int A=n;A>=2;A--){
		int B=num[A]-C;
		//区间内找出小于B的最大值的high 
		long long low=0,high=A;
		while(low+1!=high){
			int mid=(low+high)/2;
			if(num[mid]<B){
				low=mid;
			}else{
				high=mid;
			}
		}
		long long res1;
		if(num[high]!=B){ //没有这个数 
			continue; 
		}else{
			res1=high;
		}
		//cout<<res1<<" ";
		//区间内找出大于B的最小值的low 
		low=0,high=A;
		while(low+1!=high){
			int mid=(low+high)/2;
			if(num[mid]>B){
				high=mid;
			}else{
				low=mid;
			}
		}
		long long res2=low;
		cnt+=(res2-res1+1);
	}
    cout<<cnt; 
	return 0;
}
2024/5/2 16:48
加载中...