首页 > 代码库 > POJ 3579 Median
POJ 3579 Median
传送门:http://poj.org/problem?id=3579
题意
给你n个数,然后求它们两两相减的绝对值,然后找出这些绝对值的中中位数。 解题思路:
- 先对n个数排序,那么最后的结果ans一定满足0<=ans<an-a1
- 第二如何判断ans就是我们需要求的值能,我们用二分进行逼近。l=0,r=an-a1,mid=(l+r)/2;
- 二分如何逼近呢,如何判断我们要求的答案ans是在[l,mid]还是在[mid,r]部分呢?
- 很明显是原数组两个数相减的绝对值<mid个数,和>mid的个数进行比较。(绝对值的个数<mid,ans在[mid,r]区间,否则在[l,mid]区间内
- 如何判段两数绝对值<mid的个数呢?
- 如何求一个数减去a[0]的值小于mid的个数,我们找到一个a[i]>=a[0]+mid时最小的一个i,那么数组[0,i)值减去a[0],都小于mid,这样枚举i就可以求得两数相减差值小于mid的个数。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=1000005; int val[MAXN]; int N,M; bool calc(int mid){ int sum=0; //这儿如何计算绝对值<mid的个数. for(int i=0;i<N;i++) sum+=((lower_bound(val+i,val+N,val[i]+mid+1)-(val+i))-1); return sum>=M; } int main(){ while(scanf("%d",&N)!=EOF){ for(int i=0;i<N;i++){ scanf("%d",&val[i]); } M=(N*(N-1)/2+1)/2; sort(val,val+N); int l=0,r=val[N-1]-val[0]; while(r-l>1){ int mid=(l+r)>>1; if(calc(mid)) r=mid; else l=mid; } cout<<r<<endl; } return 0; }
POJ 3579 Median
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。