题目链接：点击打开链接
题目大意：两个序列合并，并输出合并后的中位数。
解题思路：
long int 数据（超过 INT_MAX）就默认为 INT_MAX，根据测试用例，最终答案不会是 long long 类型，否则就报“段错误”了，因为用的是优先队列，弹出。
当插入的个数超过中间个数值时，可以做弹出操作，最小的弹出。
注意：有可能第1序列个数很小，第2序列个数很大；也有可能反过来。
内存超限卡两种情况：i、所有数据存完；ii、数据类型太大。
MLE 代码（15分，最后一个点 MLE）
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=4*1e5+10; int a[maxn]; int main() { int n,l=0; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[l++]); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[l++]); sort(a,a+l); printf("%d\n",a[(l-1)/2]); return 0; }
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; struct cmp { bool operator()(int a,int b) { return a>b; } }; priority_queue<int,vector<int>,cmp> pq; int main() { int n,mid,ans=0,sum=0,rs,st; scanf("%d",&n); ll a; ans=sum=n; for(int i=0;i<n;i++) { scanf("%lld",&a); if(a>INT_MAX) a=INT_MAX; pq.push(a); } scanf("%d",&n); sum+=n; mid=(sum-1)/2; st=sum-mid; while(ans>st) { ans--; pq.pop(); } for(int i=0;i<n;i++) { scanf("%lld",&a); if(a>INT_MAX) a=INT_MAX; pq.push(a); ans++; if(ans>st) pq.pop(); } printf("%d\n",pq.top()); return 0; }
