首页 > 代码库 > POJ 3579 Median（二分答案+Two pointers）
POJ 3579 Median（二分答案+Two pointers）
【题目链接】 http://poj.org/problem?id=3579
【题目大意】
给出一个数列，求两两差值绝对值的中位数。
【题解】
因为如果直接计算中位数的话，数量过于庞大，难以有效计算，
所以考虑二分答案，对于假定的数据，判断是否能成为中位数
此外还要使得答案尽可能小，因为最小的满足是中位数的答案，才会是原差值数列中出现过的数
对于判定是不是差值的中位数的过程，我们用尺取法实现。
对于差值类的题目，还应注意考虑边界，即数列只有一位数的情况。
【代码】
#include <cstdio>#include <algorithm>using namespace std;int n,a[100010];int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1); int l=0,r=a[n],m=n*(n-1)/4+((n*(n-1)/2)&1),ans=0; if(n==1){puts("0");continue;} int Ans=0; while(l<=r){ int mid=(l+r)>>1,pre=1,ans=0; for(int i=2;i<=n;i++){ while(a[i]-a[pre]>mid)pre++; ans+=i-pre; }if(ans>=m)r=mid-1,Ans=mid; else l=mid+1; }printf("%d\n",Ans); }return 0;}POJ 3579 Median（二分答案+Two pointers）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。