POJ 3579 二分
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 7687 | Accepted: 2637 |
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
//两重二分,先将a数组从小到大排序,第一重二分中位数的值m,第二重枚举a[i],找到有多少
//个 |a[j]-a[i]| >= m,将这个数量与n*(n-1)/4比较作为二分的判断条件
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
int n,a[maxn];
ll k;
bool solve(int m){
ll cnt=;
for(int i=;i<n;i++){
int id=lower_bound(a+i,a+n,a[i]+m)-a;
cnt+=n-id;
}
return cnt>k;
}
int main()
{
while(scanf("%d",&n)==){
k=1LL*n*(n-)/;
for(int i=;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int l=,r=,ans;
while(l<=r){
int m=(l+r)>>;
if(solve(m)){
ans=m;
l=m+;
}else r=m-;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 【Markdown】notepad++ 支持 markdown语法、预览
- VS 2013 编译和使用 Boost
- bzoj1072
- 使用org.apache.jasper.JspC编译jsp文件--转载
- c++ 依据输入动态声明数组(一维,二维)
- HDU 1004 - Let the Balloon Rise(map 用法样例)
- 正則表達式验证邮箱,qq,座机,手机,网址
- Terminal,git,vim常用命令整理以及删除本地git仓库
- iOS中 UIMPMediaPickerController播放系统音乐
- java的数组
- python中单例模式的四种实现方式
- ES6新增的常用数组方法(forEach,map,filter,every,some)
- WebService中用CXF框架的wsdl部署生成客户端代码时,使用cmd命令口出现wsimport不是内部或外部命令的问题
- shallow clone
- SQLServer “无法对数据库&#39;XX&#39; 执行删除,因为它正用于复制”的解决方法
- FormData
- 第一章 Java Web工作原理
- 【Maven学习】Nexus OSS私服仓库的备份与迁移
- 【js】深拷贝和浅拷贝区别,以及实现深拷贝的方式
- H5 项目问题总结