POJ3579 Median —— 二分
题目链接:http://poj.org/problem?id=3579
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8286 | Accepted: 2892 |
Description
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 if m,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
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 1e5+; int n, a[MAXN];
int m; bool test(int mid)
{
int cnt = ;
for(int i = ; i<=n; i++) //注意,对于每个数,只需往一边找,否则会出现重复计算。
cnt += upper_bound(a+i+, a++n, a[i]+mid)-(a+i+); //在[i+1, n+1)的范围,即[i+1,n]
return cnt>=m;
} int main()
{
while(scanf("%d", &n)!=EOF)
{
for(int i = ; i<=n; i++)
scanf("%d", &a[i]); sort(a+, a++n);
m = n*(n-)/; //有多少个数
m = (m+)/; //中位数所在的位置
int l = , r = a[n]-a[];
while(l<=r)
{
int mid = (l+r)>>;
if(test(mid))
r = mid - ;
else
l = mid + ;
}
printf("%d\n", l);
}
}
最新文章
- RabbitMQ Topic exchange
- 大话设计模式C++版——代理模式
- 【转载】Velocity模板引擎的介绍和基本的模板语言语法使用
- session共享
- 移动硬盘安装linux系统小记
- 【Android】数据存储-java IO流文件存储
- AOP Concepts
- 创建对象时引用的关键字,assign,copy,retain
- LeetCode 二叉树的最小深度
- 记一次阿里云Linux服务器安装.net core sdk的问题以及解决方法
- Java课设(学生信息管理系统)
- 关系型数据库工作原理-事务管理(二)(翻译自Coding-Geek文章)
- Redis Rpop 命令
- Windows系统CMD下常用命令
- oracle权限列表
- Opecv + Anaconda 读取视频(windows)
- LeetCode算法题-Maximum Depth of Binary Tree
- sench touch 页面跳转
- Visual Studio进行Web性能测试- Part III
- Effective C++ 随笔(1)