Problem Description

Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the (m/2)-th ?smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.

Input

The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, ... , XN, ( Xi ≤ 1,000,000,000 ?3 ≤ N ≤ 1,00,000 )

Output

For each test case, output the median in a separate line.

Examples

Input

4
1 3 2 4
3
1 10 2

Output

1
8

題意：每組數據給出 n 個數，任意兩個數之間的差的絕對值有 C(N,2)=(n-1)*n/2 種，要求輸出這些數中間的那一個，若?C(N,2) 為偶數，中間那個數即為第?C(N,2)/2 小的數，若?C(N,2) 為奇數，中間那個數即為 第 (C(N,2)+1)/2 小的數

思路：n 是 100000，暴力的話時間復雜度能到 O(n^2) 左右，一定會超時，因此需要用二分來找

根據題意，兩個數的差取了絕對值，可看作數組 a[n] 中，任意兩個數 a[i]、a[j] 一定是大的減小的，故可以對數組先進行排序，然后根據差值來確定二分的范圍：0~a[n]-a[1]，從而進行二分

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<deque> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-6 #define INF 0x3f3f3f3f #define N 100001 #define LL long long const int MOD=998244353; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; using namespace std; int n; int a[N]; bool check(int x){int cnt=0;for(int i=0;i<n;i++){int left=i,right=n-1;while(left<=right){int mid=(left+right)>>1;if(a[mid]<a[i]+x)left=mid+1;elseright=mid-1;}cnt+=left-i-1;//cnt+=upper_bound(a,a+n,a[i]+x)-a-i-1;}int m=n*(n-1)/2;//C(n,2)m=(m+1)/2;return cnt>=m; } int main(){while(scanf("%d",&n)!=EOF&&n){for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);int left=0,right=a[n-1];while(left<=right){int mid=(left+right)/2;if(check(mid))right=mid-1;elseleft=mid+1;}printf("%d\n",right);}return 0; }

?

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的Median（POJ-3579）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。