Codeforces 1538C.Number of Pairs

题意:

给一个数组,求元组个数满足:
\(l<=a[i]+a[j]<=r,i<j\)

思路:

移项后:\(l-a[i]<=a[j]<=r-a[i]\)
二分查找即可。
注意最后答案会爆\(int\)

代码:

const int maxn=2e5+100;

int n,a[maxn],l,r;

int main(){
	int _=read;
	while(_--){
		n=read,l=read,r=read;
		rep(i,1,n) a[i]=read;
		sort(a+1,a+1+n);
		ll res=0;
		//l<=a[i]+a[j]<=r
		///l-a[i]<=a[j]<=r-a[i]
		rep(i,1,n){
			int pos1=lower_bound(a+i+1,a+1+n,l-a[i])-(a+1);
			int pos2=upper_bound(a+i+1,a+1+n,r-a[i])-(a+1);
			res+=pos2-pos1;
		}
		
		printf("%lld\n",res);
	}
	return 0;
}

Codeforces 1538C.Number of Pairs

上一篇:NX二次开发-向量乘矩阵变换的结果说明


下一篇:主席树