欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

poj 3579 Median 中间值（二分搜索）

发布时间：2025/4/16 编程问答 33 豆豆
生活随笔 收集整理的这篇文章主要介绍了 poj 3579 Median 中间值（二分搜索） 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

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 ifm,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.

Sample Input
4 1 3 2 4 3 1 10 2

Sample Output

1

8

#include <iostream> #include <cstdio> #include <algorithm> #define INF 1000000 using namespace std; int main() {int n;int a[100000];while(cin>>n){for(int i=0;i<n;++i)scanf("%d",&a[i]);int m,temp=n*(n-1)/2;if(temp&1)m=temp/2+1;elsem=temp/2; //有n个数，按照顺序排列，凉凉相减，则有n-1个数，问这n-1个数的中间值所在的位置（1......n-1排列中的位 置)m，其1、2....m的和为多少？sort(a,a+n);int low=0,high=a[n-1]-a[0];int mid,value;while(high>=low)//{int ans=0;mid=low+(high-low)/2;int pos;for(int i=0;i<n-1;++i){pos=upper_bound(a+i,a+n,mid+a[i])-a;//mid(两数之差，设定为中间值）则a[i]+mid为数组a中的中间值,pos为中间值在数组中的位置。//ans+=pos-i-1;}if(ans>=m){value=mid;high=mid-1;}elselow=mid+1;}cout<<high+1<<endl;} }

总结

以上是生活随笔为你收集整理的poj 3579 Median 中间值（二分搜索）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。