0分 二分解法 不知道该怎么调?求指教
查看原帖
0分 二分解法 不知道该怎么调?求指教
590571
_weishiqi66_楼主2022/9/30 22:18
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll a[200001];
ll n, c, ans = 0;
int lef(int l,int r,int x){
	while(l<r){
		int mid=(l+r)>>1;
		if(a[mid]>=x) r=mid;
		else l=mid+1;
	}
	if(a[l]==x) return l;
	else return 0;
}
int ref(int l ,int r,int x){
	while(l>r){
		int mid=(l+r+1)>>1;
		if(a[mid]<=x) l=mid;
		else r=mid-1;
	}
	if(a[l]==x) return l;
	else return 0;
}
void tp(){
	int li,lans;
	li=lans=0;
	sort(a+1,a+1+n);
	for(int i=1;i<n;i++){
		if(a[i]==li)
			ans+=lans;
		else{
			int t=ref(i+1,n,c+a[i])-lef(i+1,n,c+a[i]);
			if(t!=0) t++;
			li=a[i];
			ans+=t;
			lans=t;
		}
	}
	return;
}

int main() {
	cin >> n >> c;
	for (int i = 1; i <= n; i++) 
		cin >> a[i];
	
	tp();
	cout<<ans;

	return 0;
}
2022/9/30 22:18
加载中...