C. Number of Pairs

C. Number of Pairs
You are given an array a of n integers. Find the number of pairs (i,j) (1≤i<j≤n) where the sum of ai+aj is greater than or equal to l and less than or equal to r (that is, l≤ai+aj≤r).

For example, if n=3, a=[5,1,2], l=4 and r=7, then two pairs are suitable:

i=1 and j=2 (4≤5+1≤7);
i=1 and j=3 (4≤5+2≤7).
Input
The first line contains an integer t (1≤t≤104). Then t test cases follow.

The first line of each test case contains three integers n,l,r (1≤n≤2⋅105, 1≤l≤r≤109) — the length of the array and the limits on the sum in the pair.

The second line contains n integers a1,a2,…,an (1≤ai≤109).

It is guaranteed that the sum of n overall test cases does not exceed 2⋅105.

Output
For each test case, output a single integer — the number of index pairs (i,j) (i<j), such that l≤ai+aj≤r.

Example
inputCopy
4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1
outputCopy
2
7
0
1
之前没用过lower_bounder和upper_bounder 做题的时候没有想到。二分又懒得写。。。。。。
所以直接掉大分

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
int ch[205001];
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, l, r;
        cin >> n >> l >> r;
        for (int i = 0; i < n; i++)
        {
            cin >> ch[i];
        }
        sort(ch, ch + n);
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            int a = lower_bound(ch + i + 1, ch + n, l - ch[i]) - ch;
            int b = upper_bound(ch + i + 1, ch + n, r - ch[i]) - ch;
            int c = b - a;
            sum += c;
        }
        cout << sum << endl;
    }
}

哭了。。。。。。

最后

以上就是和谐鸡为你收集整理的C. Number of Pairs的全部内容，希望文章能够帮你解决C. Number of Pairs所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。