程序设计思维与实践 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 非常想得到那只可爱的猫咪，你能帮帮他吗？

题目简述：给定一个整数序列，对于任意一对数[xi xj]，i!=j，计算其差的绝对值，使其差的绝对值构成新的数列，并找出新数列的中位数。

Input：

多组输入，每次输入一个 N，表示有 N 个数，之后输入一个长度为 N 的序列 cat， cat[i] <= 1e9 , 3 <= n <= 1e5

Output：

输出新数组 ans 的中位数

思路：

暴力做法：双重循环枚举数列，计算其对应的绝对值，生成新数列，然后排序后得出中位数，时间复杂度为O(n^2)，太暴力！

考虑二分的做法，首先将cat数组排序（由小到大），那么中位数一定位于0到cat[n]之间，且是一个整数。所以就可以对中位数进行二分。二分时，对于当前的值，去进行判断，判断其是否为中位数。判断的原理是：在排好序的数列中catj-cati>=0(j>i)恒成立，则可去掉绝对值号，catj-cati<=P的数对个数，就是P在差序列中的排名，若排名恰好等于(n*(n-1)/2+1)/2，则P为中位数。用到了两次二分，即二分中位数P，然后通过二分的方法去判断P的排名。总的时间复杂度为O(logn*logn)

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,flag,a[100010];
int init()
{
	int f=1,p=0;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
	return f*p;
}
bool judge(int x)
{
	int tmp=0;
	for(int i=1;i<=n;i++)
	{
		int l=i+1,r=n,mid,j=0;
		while(l<=r)//找到最后一个使得a[j]<=a[i]+x的j 
		{
			mid=(l+r)/2;
			if(a[mid]<=a[i]+x) j=mid;
			if(a[mid]<=a[i]+x) l=mid+1;
			else r=mid-1;
		}
		if(j!=0)
		tmp+=j-i;
	}
	if(tmp>=flag) return 1;
	return 0;
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
		a[i]=init();
		sort(a+1,a+n+1);
		flag=n*(n-1)/2+1;
		flag/=2;
		int l=0,r=a[n]-a[1],mid;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(judge(mid)) r=mid-1;//P的值大了 
			else l=mid+1;
		}
		if(judge(l)) printf("%d\n",l);
		else printf("%d\n",r);
	}
	return 0;
}