社区讨论

二分RE??

P1102A-B 数对参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lvp08m3u
此快照首次捕获于
2024/05/02 16:49
2 年前
此快照最后确认于
2024/05/02 19:42
2 年前
查看原帖
CPP
#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;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...