Gym 100676E 微见解 二分思想题

链接
题意: 题意很简单,给定一个数组,问从这个数组中任意抽两个元素,要求这两个元素的绝对值之差小于32,问有多少种方法(不管顺序问题,即1和16算一种方式,没有16和1了).

思路: 第一反应是暴力每一种情况,复杂度为O(n^2)(应该吧),看给的数据范围,肯定会爆.所以就要换种方式,回到未知式|x-y|<32.x为已知数,y为满足条件的数,则y满足x-32<y<x+32,于是我的想法是将给定的数组进行排序然后找到与这个数满足条件的上限数,即这个数+32,因为是排好序(从小到大)的所以可以不用管下限,找到这个数的位置为了防止爆,就用二分法.

代码如下:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int arr[10005];
int n;
int Find(int x)
{
    int low=0,high=n,mid;
    while(low<high)
    {
        mid=(low+high)/2;
        if(arr[mid]>=x)  high=mid;
        else  low=mid+1;
    }
    return low;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        sort(arr,arr+n);
        int ans=0,tmp;
        for(int i=0;i<n;i++){
            tmp=Find(arr[i]+32);
            ans+=tmp-i-1;//这个需要注意下
        }
        printf("%d\n",ans);
    }
}