思路来源于一名大佬
题目描述
给定n个数 a1,a2,…,an，求这n个数两两的差值（共n*(n-1)/2个）的中位数。
输入输出格式
输入格式
第一行一个正整数n，表示数的个数。
接下来一行n个正整数，分别为a1,a2,…,an。
其中 2≤n≤200000，2|ai
输出格式
输出仅一行一个数表示差值的中位数。
解题思路
我们先对a序列进行一次排序
然后我们可以确定所有差的范围在0~a[n]-a[1]之间
显然中位数以及所有中位数右边的数左边都有至少n/2-1个数
相当于差值序列有单调性
就像上面这样，于是可以二分得到答案
所以写一个函数判断每个数左边有多少个数就行了
代码
代码里写有判断函数的解释
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
inline int read()
{
int ans=0,flag=0;
char ch=getchar();
while(ch<'0'||ch>'9'){flag|=ch=='-';ch=getchar();}
while('0'<=ch&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
return flag?-ans:ans;
}
ll n,a[200005];
inline ll check(ll x)
{
ll l=1,r=1,ans=0;
for(;r<=n;++r)//枚举右端点
{
while(a[r]-a[l]>x)++l;
ans+=r-l;//a[r]-a[l]<=x,因为a序列被排序过,所以a[r]-a[k]<=a[r]-a[l]<=x(l<k<r)
}
return ans;//x左边有ans个数
}
inline ll Er(ll x)
{
ll l=0,r=a[n]-a[1];
while(l<=r)
{
ll mid=l+r>>1;
check(mid)<x?l=mid+1:r=mid-1;
}
return l;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
ll num=n*(n-1)/2;//细节,如果num是偶数,中位数是中间两个数的和除以2
num%2?printf("%lld",Er(num/2)):printf("%lld",(Er(num/2)+Er(num/2+1))/2);
return 0;
}
/*
3
4 2 6
*/
花开·花落--便是一生 