POJ 3579:Median 差值的中位数
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 4680 | Accepted: 1452 |
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
题意是给出一个数组,然后这些数组元素每一对之间都有一个差值,找出这些差值的中位数。
两次二分,第一次二分是枚举答案,第二次二分是我觉得很好玩的地方,在给定的差值下,找到多少个对的差值小于等于它,用这样的二分来判断这个差值在所有的差值中的位置。感觉很巧妙~
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std; int num,m;
int val[100005]; bool check(int mid)
{
int i,sum=0; for (i = 0; i < num; i++)
{
sum += (lower_bound(val + i, val + num, val[i] + mid + 1) - (val + i) - 1);
}
if (sum >= m)
{
return true;
}
else
{
return false;
}
} int main()
{
//freopen("i.txt","r",stdin);
//freopen("o.txt","w",stdout); int i,left,right,mid;
while (scanf("%d", &num) != EOF)
{
for (i = 0; i < num; i++)
{
scanf("%d", &val[i]);
}
m = (num*(num - 1) / 2 + 1) / 2;
sort(val,val+num); left = 0;
right = val[num - 1] - val[0]; while (right-left > 1)
{
mid = (left + right) / 2; if (check(mid))
{
right = mid ;
}
else
{
left = mid ;
}
}
cout << right << endl;
}
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- .net基础复习之一
- JAVA设计模式--工厂方法模式
- java:读/写配置文件
- FineUI小技巧(1)简单的购物车页面
- [NOIP2012] 提高组 洛谷P1079 Vigen&#232;re 密码
- Code First 中使用 ForeignKey指定外键时总是显示未引用
- 骨牌铺方格[HDU2046]
- Currency Exchange 分类: POJ 2015-07-14 16:20 10人阅读 评论(0) 收藏
- POJ 2942 Knights of the Round Table (点双连通分量)
- Ubuntu Kylin14.04终于可以使用root登陆了
- 动态sql语句基本语法
- C++拷贝对象
- 《JavaScript设计模式与开发实践》读书笔记之享元模式
- 【BZOJ4825】【HNOI2017】单旋(Link-Cut Tree)
- 高校学生征信系统Postmortem结果
- 根据http协议下载文件保存到相应的文件下
- POJ - 3468 线段树区间修改,区间求和
- pta l2-11(玩转二叉树)
- # 2017-2018-2 20155319『网络对抗技术』Exp2:后门原理与实践
- 使用ggbio在R中制作弦图