TT 是一位重度爱猫人士，每日沉溺于 B 站上的猫咪频道。
有一天，TT 的好友 ZJM 决定交给 TT 一个难题，如果 TT 能够解决这个难题，ZJM 就会买一只可爱猫咪送给 TT。
任务内容是，给定一个 N 个数的数组 cat[i]，并用这个数组生成一个新数组 ans[i]。新数组定义为对于任意的 i, j 且 i != j，均有 ans[] = abs(cat[i] - cat[j])，1 <= i < j <= N。试求出这个新数组的中位数，中位数即为排序之后 (len+1)/2 位置对应的数字，’/’ 为下取整。
TT 非常想得到那只可爱的猫咪，你能帮帮他吗？
多组输入，每次输入一个 N，表示有 N 个数，之后输入一个长度为 N 的序列 cat， cat[i] <= 1e9 , 3 <= n <= 1e5
输出新数组 ans 的中位数
4
1 3 2 4
3
1 10 2
1
8
该题利用了二分答案P，枚举+二分计算P的名次的方法
复杂度为
怎样计算P的名次？
如果将X从小到大排列可以去绝对值。
那么计算𝑋𝑗−𝑋𝑖≤𝑃的二元组对数即可。
移项可得𝑋𝑗≤𝑋𝑖+𝑃, 𝑖<𝑗
枚举下标i然后计算满足条件的下标j的个数 也可以二分！
当然我们也可以换个角度来思考一下
想象存在这样一个数组，这个数组的前半部分全是1，后半部分全是0
这个数组可以有这样的含义
如果a[i]=1，表明当p=i的时候，p的排名小于中位数
如果a[i]=0，表明当p=i的时候，p的排名等于或大于中位数
R为最大可能的答案，在这个题中可以是数列B的最大值，也就是数列X中最大值和最小值的差
如果从这个角度来考虑的话，X就是我们要的答案
我们的任务变成了求这个数组中第一个0出现的位置
本题使用了二分答案和普通二分法，二分答案意味着找到答案的可行区间进行二分，可行区间内的点不一定都是满足条件的取值，但一定包括所有满足条件的取值。
step0 将所有数录入到数组ans中并按从小到大排序，这样后面的数一定会大于前面的数，作差时用后面的数减去前面的数即可得到绝对值
step1 用ans两头数相减作为max，0为min，在max和min之间进行二分，取p=(min+max)>>1，调用函数count（int p）计算ans中任意两值相减的绝对值中值<=p的个数，找到一个最小的p其count(int p)>=新数组长度的一半，该p即为所求中位数
step2 count(int p)中用i遍历ans数组，对i~n-1进行二分，找到最大的一个使ans[j]-ans[i]>=p的值，另sum+=(j-1)，当i遍历完ans数组后，sum中存储的即为所求的ans中任意两值相减的绝对值中值<=p的个数。
1、注意中位数的下标是新生成的数组的中位数，要先求出生成新数组的长度len，再用（len+1）/2得中位数的位置，不要错用成原数组的长度n，用(n+1)/2求。
2、其他两个错误注释在代码中。
#include<iostream>
#include<algorithm>
using namespace std;
int ans[100000],n;
int count(int p)
{
int sum=0;
for(int i=0;i<n;i++)//可进行剪枝
{
int l=i,r=n-1,j=-1;//注意这里r应该为n-1，若为n，可能二分时恰好为n，之后若再+1会越界
while(l<=r)
{
int mid=(l+r)>>1;
if(ans[mid]<=ans[i]+p)
{
j=mid;
l=mid+1;
}
else r=mid-1;
}
if(j!=-1)
{
sum+=(j-i);//注意j-i才是增加的绝对值个数，而非j+1
// cout<<"sum"<<sum<<endl;
}
}
return sum;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d",&ans[i]);
sort(ans,ans+n);
int max=ans[n-1]-ans[0],min=0,zw,len=n*(n-1)/2;
// cout<<"len:"<<len<<endl;
// cout<<max<<' '<<min<<endl;
while(min<=max)
{
int p=(min+max)>>1;
// cout<<"p"<<p<<endl;
// cout<<"count(p)"<<count(p)<<endl;
if(count(p)>=(len+1)/2)
{
zw=p;
max=p-1;
}
else min=p+1;
}
printf("%d\n",zw);
}
return 0;
}