首页 > 代码库 > URAL1306 Sequence Median(卡内存神题)
URAL1306 Sequence Median(卡内存神题)
给出n个数,n<=250000,求这n个数的中位数,内存限制1mb
卡内存的神题,用数组存下来刚好1mb,再加上执行时消耗内存。立即爆。
因此我们用优先队列存储一半的数。
网上的某些代码,用priority_queue全爆内存。
我存的125000长度的数组。加上STL的make_heap()
#include<cstdio> #include<queue> using namespace std; int a[125010]; int main() { int n,x; double ans; scanf("%d",&n); for(int i = 0; i < n/2+1; i++) scanf("%d",&a[i]); make_heap(a,a+n/2+1); for(int i = n/2+1; i < n; i++) { scanf("%d",&x); if(x<a[0]) { pop_heap(a,a+n/2+1); a[n/2] = x; push_heap(a,a+n/2+1); } } if(n&1) ans = (double)a[0]; else { ans = (double)a[0]; pop_heap(a,a+n/2+1); ans += (double)a[0]; ans = ans/2.0; } printf("%.1lf\n",ans); }
URAL1306 Sequence Median(卡内存神题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。