首页 > 代码库 > POJ 3579 Median

POJ 3579 Median

传送门:http://poj.org/problem?id=3579

技术分享

技术分享

题意

给你n个数,然后求它们两两相减的绝对值,然后找出这些绝对值的中中位数。 解题思路:

  1. 先对n个数排序,那么最后的结果ans一定满足0<=ans<an-a1
  2. 第二如何判断ans就是我们需要求的值能,我们用二分进行逼近。l=0,r=an-a1,mid=(l+r)/2;
  3. 二分如何逼近呢,如何判断我们要求的答案ans是在[l,mid]还是在[mid,r]部分呢?
  4. 很明显是原数组两个数相减的绝对值<mid个数,和>mid的个数进行比较。(绝对值的个数<mid,ans在[mid,r]区间,否则在[l,mid]区间内
  5. 如何判段两数绝对值<mid的个数呢?
  6. 如何求一个数减去a[0]的值小于mid的个数,我们找到一个a[i]>=a[0]+mid时最小的一个i,那么数组[0,i)值减去a[0],都小于mid,这样枚举i就可以求得两数相减差值小于mid的个数。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1000005;
int val[MAXN];
int N,M;


bool calc(int mid){
    int sum=0;
    //这儿如何计算绝对值<mid的个数.
    for(int i=0;i<N;i++)
        sum+=((lower_bound(val+i,val+N,val[i]+mid+1)-(val+i))-1);
    return sum>=M;
}

int main(){
    while(scanf("%d",&N)!=EOF){

    for(int i=0;i<N;i++){
        scanf("%d",&val[i]);
    }
    M=(N*(N-1)/2+1)/2;
    sort(val,val+N);
    int l=0,r=val[N-1]-val[0];

    while(r-l>1){
        int mid=(l+r)>>1;
        if(calc(mid))
            r=mid;
        else
            l=mid;
    }
    cout<<r<<endl;
    }
    return 0;
}

 

POJ 3579 Median