血的教训：
1. 尽信题解，不如无题解！
2. C++ STL很坑爹。。
3. 题解很坑爹。。。
测试结果分析与比较：
#1是我自己写的，使用priority_queue，超内存：
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; priority_queue <unsigned int> pq; int main(){ unsigned int n,i,x,s1,s2; scanf("%d",&n); if(n % 2 != 0){ for(i=1;i<=n;i++){ scanf("%d",&x); pq.push(x); if(pq.size() == n/2+2){ pq.pop(); } } printf("%.1lf ",(double)pq.top()); } else{ for(i=1;i<=n;i++){ scanf("%d",&x); pq.push(x); if(pq.size() == n/2+2){ pq.pop(); } } s1 = pq.top(); pq.pop(); s2 = pq.top(); printf("%.1lf ",(double)(s1+s2)/2); } return 0; }
#2 from PegasusWang http://www.cnblogs.com/PegasusWang/archive/2013/03/23/2977597.html
使用priority_queue,同样超内存
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue> //for priority_queue
using namespace std;
int main()
{
priority_queue<unsigned int> ipq;
int n;
scanf("%d", &n);
unsigned int t;
for (int i = 1; i <= n / 2 + 1; ++i)
{
scanf("%u", &t);
ipq.push(t);
}
int tn = n / 2 + 2;
while (tn <= n)
{
scanf("%u", &t);
ipq.push(t);
++tn;
ipq.pop();
}
if (n & 1) //if n is odd
printf("%u.0
", ipq.top());
else
{
int t1 = ipq.top();
ipq.pop();
printf("%.1f", (double)(t1 + ipq.top()) / 2);
}
return 0;
}
#3 from 不许偷懒啦小鬼 http://blog.csdn.net/yujuan_mao/article/details/7985424
使用priorty_queue，还是超内存
#include<cstdio> #include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; int main(){ unsigned int n,temp,i,j,k,m,x,y; priority_queue<unsigned int,vector<unsigned int>,greater<unsigned int> > Q; cin>>n; for(i=0;i<n;i++){ scanf("%u",&m); Q.push(m); if(Q.size()>(n/2+1)) Q.pop(); } if(n%2) printf("%.1lf ",1.0*Q.top()); else{ x=Q.top(); Q.pop(); y=Q.top(); printf("%.1lf ",1.0*(x+y)/2); } return 0; }
#4 from http://www.zgxue.com/163/1639818.html
使用静态数组 +heap，AC
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int maxn=250000; int a[maxn/2+10]; int main() { int n;double ans; while(scanf("%d",&n)!=EOF) { int num=0,x; 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%2) { ans=(double)a[0]; printf("%.1lf ",ans); } else { ans=(double)a[0]; pop_heap(a,a+n/2+1); ans+=(double)a[0]; printf("%.1lf ",ans/2.0); } } return 0; }
#5 自己写的，使用动态数组 + heap ，依然超内存
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; vector <unsigned int> v; int main(){ unsigned int n,i,x,s1,s2; scanf("%d",&n); if(n % 2 != 0){ for(i=1;i<=n/2+1;i++){ scanf("%d",&x); v.push_back(x); } make_heap(v.begin(),v.end()); for(;i<=n;i++){ scanf("%d",&x); v.push_back(x); push_heap(v.begin(),v.end()); pop_heap(v.begin(),v.end()); v.pop_back(); } printf("%.1lf ",(double)v.front()); } else{ for(i=1;i<=n/2+1;i++){ scanf("%d",&x); v.push_back(x); } make_heap(v.begin(),v.end()); for(;i<=n;i++){ scanf("%d",&x); v.push_back(x); push_heap(v.begin(),v.end()); pop_heap(v.begin(),v.end()); v.pop_back(); } s1 = v.front(); pop_heap(v.begin(),v.end()); v.pop_back(); s2 = v.front(); printf("%.1lf ",(double)(s1+s2)/2); } return 0; }
#6 自己写的，使用静态数组 +heap，AC
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; unsigned int a[125005]; int main(){ unsigned int n,i,x,s1,s2; scanf("%d",&n); if(n % 2 != 0){ for(i=0;i<n/2+1;i++){ scanf("%d",&a[i]); } make_heap(a,a+n/2+1); for(i=n/2+1;i<n;i++){ scanf("%d",&x); a[n/2+1]=x; push_heap(a,a+n/2+2); pop_heap(a,a+n/2+2); } printf("%.1lf ",(double)a[0]); } else{ for(i=0;i<n/2+1;i++){ scanf("%d",&a[i]); } make_heap(a,a+n/2+1); for(i=n/2+1;i<n;i++){ scanf("%d",&x); a[n/2+1]=x; push_heap(a,a+n/2+2); pop_heap(a,a+n/2+2); } s1 = a[0]; pop_heap(a,a+n/2+1); s2 = a[0]; printf("%.1lf ",(double)(s1+s2)/2); } return 0; }
#7 from cz908640443 http://blog.163.com/cz_insane/blog/static/22046718520134234472659/
使用动态数组 + heap ，超内存
#include <iostream> #include <algorithm> #include <vector> #include <cstdio> using namespace std; int i, n, temp, num[1]; long long ans; int main(){ cin>>n; cin>>num[0]; vector<int> v(num, num + 1); for (i = 1; i < n / 2 + 1; i++){ cin>>temp; v.push_back(temp); push_heap(v.begin(), v.end()); } if (n % 2) { make_heap(v.begin(), v.end()); for (i = n / 2 + 1; i < n; i++) { cin>>temp; v.push_back(temp); push_heap(v.begin(), v.end()); pop_heap(v.begin(), v.end()); v.pop_back(); } printf("%.1lf ",(double)v.front()); } else { make_heap(v.begin(), v.end()); for (i = n / 2 + 1; i < n; i++) { cin>>temp; v.push_back(temp); push_heap(v.begin(), v.end()); pop_heap(v.begin(), v.end()); v.pop_back(); } ans = v.front(); pop_heap(v.begin(), v.end()); v.pop_back(); ans += v.front(); printf("%.1lf ",(double)ans/2); } return 0; }
从以上代码1~7 得到结论：priority_queue 1000KB+会超出内存，动态数组 + heap 1000KB+也会超出内存，只有静态数组 +heap 1000KB以下，不超内存
这是为什么呢？
The standard container adaptor priority_queue calls make_heap, push_heap and pop_heap automatically to maintain heap properties for a container.
当初听说STL饱受诟病还不解，现在明白了，对于STL，如果没有领会其本质就乱用，得不偿失