POJ 3579
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 3528 | Accepted: 1001 |
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 <algorithm> using namespace std; #define maxn 100005
#define INF 200005
typedef long long ll; int n;
int a[maxn],dis[maxn];
ll num; bool judge(int x) { int pos,i = ,now = ;
ll sum = ;
while(i < n) {
pos = upper_bound(dis + ,dis + n + ,x + now) - dis;
sum += n - (pos);
now = dis[i];
if((n - ) - pos + == ) break;
++i;
} //printf("x = %d sum = %lld\n",x,sum); return num - sum - (num % ) >= sum;
} void solve() { num = (ll)n * (n - ) / ; int l = INF,r = a[n] - a[];
for(int i = ; i < n; ++i) {
dis[i] = a[i + ] - a[];
l = min(l,a[i + ] - a[i]);
// printf("%d ",dis[i]);
}
dis[n] = INF; //printf("l = %d r = %d\n",l,r); while(l < r) {
int mid = (l + r) >> ;
if(judge(mid)) {
r = mid;
} else {
l = mid + ;
}
} printf("%d\n",l); } int main()
{
// freopen("sw.in","r",stdin); while(~scanf("%d",&n)) {
for(int i = ; i <= n; ++i) {
scanf("%d",&a[i]);
} sort(a + ,a + n + ); solve();
} return ;
}
最新文章
- Android之SQLite数据存储
- java中的注解(Annotation)
- C程序中对时间的处理——time库函数详解
- 怎么解决Android studio导入项目卡死
- timeSeries db之:使用Metrics监控应用程序的性能 (zz)
- (转载)OC学习篇之---类的三大特性:封装,继承,多态
- CASS转ARCGIS
- HTML5学习(五)----SVG
- Ext.Net学习笔记18:Ext.Net 可编辑的GridPanel
- MVC零基础学习整理(一)
- mysql数据库事务详细剖析
- windows平台下cocos2d-x-3.0beta2创建新项目
- MySQL的一些常用的SQL语句整理
- IDEA破解 Intellij IDEA license server 激活(可用)
- linux安装redis操作
- 阿里面试题BIO和NIO数量问题附答案和代码
- repr方法字符串输出实例对象的值
- ASP.NET MVC 5 开发环境配置
- Maven配置本地仓库
- poj2299——Ultra-QuickSort