poj 3579 Median (尺取法+二分)

Posted by 111qqz on Monday, September 19, 2016

TOC

题意:给出n个数,两两做差的绝对值,共有m=n*(n-1)/2个,问其中的中位数是多少。特别地,当m为偶数的时候,中位数为第m/2个。

思路:二分中位数。

一开始还觉得由于中位数在整数意义上不连续不能二分。。。。

但是最后结果不可能是那样的答案啊。。。

check的条件是,以k为中位数的时候,绝对值小于k的数要小于(m+1)/2个(也就是中位数所在的位置)

check的时候尺取即可。

复杂度 排序O(nlgn) + 二分(lgn)*尺取O(n) ,整体O(nlgn)

/* ***********************************************
Author :111qqz
Created Time :Tue 20 Sep 2016 12:18:19 AM CST
File Name :code/poj/3579.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
LL n,m;
int x[N];
bool check( int k) 
{
    int cnt = 0 ; //cnt为绝对值小于k的对数,小于中位数的对数应该小于m个。
    int head = 1;
    int tail = 1;
    while (head<=n)
    {
    while (x[tail]-x[head]<k&&tail<=n) tail++;
    tail--;
    cnt+=(tail-head);
    head++;
    }
    return cnt>=m;
}
int bin()
{
    int l = 0 ;
    int r = x[n] - x[1];
    while (l<=r)
    {
    int mid = (l+r)>>1;
    if (check(mid)) r = mid-1;
    else l = mid+1;
    }
    return l-1;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    while (scanf("%lld",&n)!=EOF){
        for ( int i = 1 ; i <= n ; i++	) scanf("%d",&x[i]);
        sort(x+1,x+n+1);
        m = n*(n-1)/2;
        m = (m+1)/2;
        int ans = bin();
        printf("%d\n",ans);
    }
#ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付