(POJ - 3579) median (two points)

  Chinese question meaning ： Now there is N A mysterious number （A1,A2,A3….An）, We need to get a password from this string of numbers .
The way to get the password is ：
First calculate the difference between each number ：|Ai-Aj|(1<=i<j<=N), In the end, you can get C Difference .
The final password is the median of these numbers .
If C It's even , It is stipulated that the median is C/2 Small difference .

This question and POJ-3579 The method of question is similar , We also solve it by dichotomy , For each number to be bisected x, We go through check Function to determine whether it is less than or equal to x How many pairs of distances are there , If the distance is less than or equal to x The number of pairs of is greater than half of the logarithm of the total , that r=x, conversely l=x+1, How should the specific dichotomy be carried out ？ Let's start with a Sort the array from small to large , The dichotomy is found in ai On the right and the distance is less than or equal to x The number of , because aj-ai It is monotonically increasing , So this process is carried out through dichotomy , Traverse in turn ai, The distance is less than x Number to number , Two points are enough , There are quite a lot of details , See the code for details ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1000003;
int a[N],n;
bool check(int x)// Find that the distance is less than or equal to x How many pairs are there , More than half the logarithm of all numbers returns true, Otherwise return to false
{
	int cnt=0;
	for(int i=1;i<=n;i++)
		cnt+=upper_bound(a+1,a+n+1,a[i]+x)-a-i-1;
	if(cnt>=((long long)n*(n-1)/2+1)/2) return true;
	return false;
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		int l=0,r=1000000000,mid;
		while(l<r)
		{
			mid=l+r>>1;
			if(check(mid)) r=mid;
			else l=mid+1;
		}
		printf("%d\n",l);
	}
	return 0;
}