week4作业-C-TT的神秘礼物

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^2，e18太高了。
这个题需要两层二分。首先我们把cat数列从小到大排序去掉绝对值号，那么ans=cat[j]-cat[i],对于我们要找的中位数p，它的范围为0到cat[n-1]-cat[0],所以我们不用枚举，用二分的方法先从（cat[n-1]-cat[0])/2开始找，那么问题来了，怎么判断中位数是否大于mid呢？判断名次是否高于mid就可以了，也就是说判断小于mid的数的个数是否大于中位数的名次，而中位数的名次就是(sizeof(ans)+1)/2,所以我们只需要找到小于mid的数的个数就好了即a[j]-a[i]<=mid，这里用到我们第二层二分，移项得到a[j]<=a[i]+mid,我们遍历i，对于每个i我们用二分找出第一个大于a[i]+mid的数就好了。

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int bisearch(int *a,int left,int right,int num)
{
	int ans=right+1; 
	while(left<=right)
	{
		int mid=(left+right)>>1;
		if(a[mid]>=num)
		{
			ans=mid;
			right=mid-1;
		}
		else left=mid+1;
	}
	return ans;
 } 
 int main()
 {
 	int n;
 	while(~scanf("%d",&n))
 	{
 		int *cat=new int[n];
 		for(int i=0;i<n;i++)
 		{
 			scanf("%d",&cat[i]);
		 }
		 sort(cat,cat+n);
		 int l=0,r=cat[n-1]-cat[0];
		 int ansm=((n-1)*n/2+1)/2;
		 while(l<=r)
		 {
		 	int mid=(l+r)>>1;
		 	int rk=0;
		 	for(int i=0;i<n;i++)
		 	{
		 		rk+=n-bisearch(cat,0,n-1,cat[i]+mid);
			 }
			 if(rk>((n-1)*n/2-ansm)) l=mid+1;
			 else r=mid-1;
		 }
		 cout<<l-1<<endl;
	 }
	 return 0;
 }