CF1538C Number of Pairs

传送门

题目大意

给一个数列和 $l$，$r$ 两个数，问在序列中的两个数的和有多少个在 $[l,r]$ 的区间中。

---

思路

首先，我们要对这个序列从小到大排序。然后思考，我们从序列最小的数开始遍历，从最大的数开始逆着遍历，两者加和如果小于等于 $r$ 开始计数，这样我们的右边界就处理好了。

接着是左边界，我们刚刚计数记的是小于等于 $r$ 的数的个数，其中包括了小于 $l$ 的数量，所以我们可以再计一次，计小于 $l$ 的数量，这次计的数要减掉，因为他们不符合题意。

---

细节优化

遍历的时候因为是两个数的加和，在考虑边界的时候要注意 $l<r$，当加和时左右边界相遇时可以直接跳出循环。

注意：

在计右边边界时，要加上计的数。在计左边界时，要减去计的数。

---

代码

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cmath>
using namespace std;
int t,n;//t组数据 n个元素 
int a_a[200001];//存储元素 
int l,r;//左右边界 
void get_ans(){
  long long ans=0;//结果 
  for(int i=0,j=n-1;i<j;i++){//右边界遍历 
    while(i<j&&a_a[i]+a_a[j]>r)j--;//寻找加和小于r的右边界 
    if(j-i<0)break;//跳出循环 
    ans+=j-i;
  }
  for(int i=0,j=n-1;i<j;i++){//左边界遍历 
    while(i<j&&a_a[i]+a_a[j]>=l)j--;
    if(j-i<0)break;
    ans-=j-i;
  }
  cout<<ans<<endl;//输出结果 
}
int main(){
  scanf("%d",&t);
  while(t--){
    scanf("%d %d %d",&n,&l,&r);
    for(int i=0;i<n;i++)scanf("%d",&a_a[i]);
    sort(a_a,a_a+n);//从小到大排序 
    get_ans();
  }
  return 0; 
}