POJ3579题解二分搜索+调用函数

题目链接：http://poj.org/problem?id=3579

GivenNnumbers,X₁,X₂, ... ,X_N, let us calculate the difference of every pair of numbers: ∣X_i-X_j∣ (1 ≤i＜j≤N). We can getC(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 ofm= 6.

Input

The input consists of several test cases.
In each test case,Nwill be given in the first line. ThenNnumbers are given, representingX₁,X₂, ... ,X_N, (X_i≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

Output

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

Sample Input

Sample Output

1
8

题目意思：在n个数字中找出两两差值（绝对值）的中位数。

首先要了解一下lower_bound()这个函数，它是一个能够找出递增序列中第一个大于等于某个数的函数，它和upper_bound()相对应。不知道的戳这里：https://www.cnblogs.com/Tang-tangt/p/9291018.html

解题思路：首先我们要知道，n个数存在n*（n-1）/2个差值（组合数），而这个数量级就已经达到了十次方，所以我们无法直接存差值。正确的解法是二分列举差值，如果超过这个差值的组合数超过总组合数的一半，则中位数必定比该差值更大，反之则更小。

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
int n, m;
bool test(int val)
{
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        cnt+=n-(lower_bound(a,a+n,a[i]+val)-a);//a[i]对应的(即与a[i]形成差值)原序列中比a[i]+val大的元素个数（也即是部分组合数） 
    }
    return cnt>m;//如果大于差值val的对应的组合总数超过了一半 
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
         m=n*(n-1)/4;
         for(int i=0;i<n;i++)
             scanf("%d",&a[i]);
         sort(a,a+n);
         int l=0,r=a[n-1]-a[0];
         while(r-l>1)
         {
             int mid=(l+r)>>1;
             if(test(mid))l=mid;//如果val对应差值组合数超过一半则所有差值的中位数必然比mid更大 
             else r=mid;
         }
         printf("%d\n",l);
    }
    return 0;
}

View Code

优质内容筛选与推荐>>
1、python 写的http后台弱口令爆破工具
2、前端开发页面的性能优化方案总结
3、如何在大量jar包中搜索特定字符
4、Linux网络编程一步一步学-异步通讯聊天程序select
5、git学习笔记（五）--git的重置

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看