题目大意：
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 非常想得到那只可爱的猫咪，你能帮帮他吗？
Input
多组输入，每次输入一个 N，表示有 N 个数，之后输入一个长度为 N 的序列 cat， cat[i] <= 1e9 , 3 <= n <= 1e5
Output
输出新数组 ans 的中位数
Sample Input
4 1 3 2 4 3 1 10 2
Sample Output
1 8
思路：两次二分-淋漓尽致
这道题目知道是用二分的思想做，但是做的时候却卡了好几天，怎么二分呢？
这个时候就要回到中位数的定义中去：大小排序后最中间位置，即(n*(n-1)/2+1)/2
新数组中最大数为原数组中最大数与最小数之差，然后可以对这个值二分。要判断其在新数组中的位置，即找在新数组中有多少比他大或小。
这一步又要用到二分的思想，对于固定的数，找满足条件的数的个数（原数组二分 找满足差的个数 ）
1 /* 2 Name: 3 Copyright: 4 Author:sduAllen 5 Date: 19/03/20 11:44 6 Description: 7 */ 8 9 #include<iostream> 10 #include<stdio.h> 11 #include<algorithm> 12 #include<cmath> 13 using namespace std; 14 15 //const int max = 1e5+1; 16 int *cat = new int[100001]; 17 int N; 18 int last_index(int start){ //找到最后一个满足小于等于start的位置索引 19 int l=0,r=N-1,index=-1; 20 while(l<=r){ 21 int mid = (l+r)/2; 22 if(cat[mid]<=start){ 23 index=mid; 24 l=mid+1; 25 } 26 else 27 r=mid-1; 28 } 29 return index; 30 } 31 32 int main(){ 33 34 while(scanf("%d",&N)!= EOF){ 35 for(int i=0;i<N;i++) 36 scanf("%d",&cat[i]); 37 sort(cat,cat+N); 38 39 int ans_Mid = (N*(N-1)/2+1)/2; 40 int themid; 41 int l=0,r=cat[N-1]-cat[0]; //新数组的最大最小值 42 43 while(l<=r){ //在0~max之间二分 44 int cnt = 0,mid = (l+r)/2; //cnt计算在新数组中的位置 45 for(int i=0;i<N;i++){ 46 int index = last_index(cat[i]+mid); 47 if(index!=-1) 48 cnt += index-i; 49 } 50 if(cnt >= ans_Mid){ 51 themid = mid; 52 r=mid-1; 53 } 54 else 55 l=mid+1; 56 } 57 printf("%d ",themid); 58 } 59 return 0; 60 }