放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

POJ 3579 Median 题解 《挑战程序设计竞赛》

目录

POJ 3579 Median

双重二分搜索:对列数X计算Xi  Xj组成新数列的中位数。

3.1不光是查找值!“二分搜索”

查找第k大的值

对X排序后,与X_i的差大于mid(也就是某个数大于X_i + mid)的那些数的个数如果小于N / 2的话,说明mid太大了。以此为条件进行第一重二分搜索,第二重二分搜索是对X的搜索,直接用lower_bound实现。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
#define MAX_N 100000 + 16
ULL N;
ULL C_N_2;
int X[MAX_N];

// mid作为中位数是否太大
bool C(const int& mid)
{
	ULL bigger_count = 0;
	for (int i = 0; i < N; ++i)
	{
		bigger_count += X + N - lower_bound(X + i + 1, X + N, mid + X[i]);	// 返回大于或等于val的第一个元素位置
	}

	return bigger_count <= C_N_2 / 2;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	while (cin >> N)
	{
		for (int i = 0; i < N; ++i)
		{
			scanf("%d", X + i);
		}
		sort(X, X + N);
		C_N_2 = N * (N - 1) / 2;
		ULL lb = 0, ub = *max_element(X, X + N) - *min_element(X, X + N) + 1;
		while (ub - lb > 1)
		{
			int mid = (lb + ub) >> 1;
			if (C(mid))
			{
				ub = mid;
			}
			else
			{
				lb = mid;
			}
		}
		cout << lb << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

12835934 hankcs 3579 Accepted 360K 579MS C++ 1190B 2014-05-04 03:11:35

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 3579 Median 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 5

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    题主,C()那里可以用尺取法来计算小于等于mid的个数 =V= 时间可以少一半
    int p = 0;
    for(int i = 1; i < N; i++){
    for(int j = p; j < i; j++){
    if(X[i] – X[j] <= x){
    res += i – j;
    p = j;
    break;
    }
    }
    }

    return res;

    will1年前 (2016-01-01)回复
    • 不好意思,if里的x就是mid

      will1年前 (2016-01-01)回复
  2. #1

    根据题目描述,好像这组数据是过不了的:
    2
    -1000000000 1000000000

    我的AC程序也过不了这组数据,始终不知道如果考虑这组数据的话,怎样才能过掉题目而且还不会TLE。。请问博主有什么好的想法么??

    wt2年前 (2015-10-03)回复
    • ub的初始值小了而已,有负数的情况下改成
      int lb = 0, ub = *max_element(X, X + N) – *min_element(X, X + N) + 1;
      就行了。另外1000000000会溢出,改成ULL就行了。

      hankcs2年前 (2015-10-03)回复
      • 表示本弱就是这样做的, 然后TLE无数。。T^T,总感觉自己姿势不对。。

        wt2年前 (2015-10-03)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机