Median

Descriptions

给N数字, X₁, X₂, ... , X_N，我们计算每对数字之间的差值：∣X_i - X_j∣ (1 ≤ i ＜ j ≤N). 我们能得到 C(N,2) 个差值，现在我们想得到这些差值之间的中位数。

如果一共有m个差值且m是偶数，那么我们规定中位数是第(m/2)小的差值。

Input

输入包含多测
每个测试点中，第一行有一个NThen N 表示数字的数量。
接下来一行由N个数字：X₁, X₂, ... , X_N
( X_i≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

Output

对于每个样例，输出中位数即可。

Sample Input

Sample Output

1

8

题目链接

https://vjudge.net/problem/POJ-3579

注意这里不能直接把所有数的差都保存下来，直接输出，这样数组会爆掉，我卡了好长时间

老老实实用二分去求中位数把

C²_n的求法是 n*(n-1)/2，即一共这么多差中间那个差也就是中位数就是n*(n-1)/4

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 100000+5

using namespace std;

ll n,m;

ll l,r,mid;

ll a[Maxn];

int judge(int x)

{

    ll cnt=;//统计小于x的差有多少

    for(int i=; i<n; i++)

        cnt+=n-(lower_bound(a,a+n,a[i]+x)-a);

    return cnt>m;//大于一半

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        m=n*(n-)/;

        for(int i=; i<n; i++)

            scanf("%d",&a[i]);

        sort(a,a+n);

        l=,r=a[n-]-a[];

        while(r-l>)//如果是 r>l的话，因为是整除最后会卡死

        //举个例子 l=1,r=2 块就会被卡死

        {

            mid=(l+r)/;

            if(judge(mid))

                l=mid;

            else

                r=mid;

        }

        printf("%d\n",l);

    }

    return ;

}

秒客网

【POJ - 3579 】Median（二分）

Median

相关文章