正文
PAT甲题题解-1029. Median (25)-求两序列的中位数，题目更新了之后不水了
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
这个是原先AC的代码，但是目前最后一个样例会超内存，也就是开不了两个数组来保存两个序列了，意味着我们只能开一个数组来存，这就需要利用到两个数组都有序的性质了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
/*
水死了
*/
const int maxn=+;
int seq[maxn];int main()
{
int n1,n2;
scanf("%d",&n1);
for(int i=;i<n1;i++){
scanf("%d",&seq[i]);
}
scanf("%d",&n2);
for(int i=;i<n2;i++){
scanf("%d",&seq[n1+i]);
}
sort(seq,seq+n1+n2);
int n=n1+n2;
int mid;
if(n%==){
mid=n/;
}
else{
mid=n/+;
}
printf("%d\n",seq[mid-]);
return ;
}
由于直接开4*10^5的数组，最后一个样例会超出内存，所以显然应该只能保存一个数组，不能两个都保存。
那么这就要利用到两个数组都是有序的性质了。
拿例子来说吧
Case1：
4 11 12 13 14 mid
5 9 10 15 16 17
方便起见，第一个数组为seq1，第二个数组seq2，整个数组seq12，我们可以将seq1理解为seq12的前一半数组。
我们先存第一个数组，存入到seq1里面
mid为中位数索引，这里mid=(4+5+1)/2-1=4，即seq1[4]。
但由于此时seq1[4]上是没有数字的，我们又设定了一个target=n1-1，即读取seq2的时候，会和seq1[target]比较值
1.mid=4,target=3
2.读取9,9<seq1[target],那么意味着9我可以插入到seq12的前一半数组中去，前一半数组多了一个元素，mid肯定要-1。
mid=mid-1=3,target=3
3.读取10,10<seq1[target]，同样的，10也可以插入到前一半中去
mid=mid-1=2，由于此时mid<target了，所以也要更新下target=target-1=2，现在target和mid就指向同一个了
4.读取15，15是大于seq1[target]的，那也就是意味着，后面所有的数都是大于seq1[target]的，那么中位数显然就是seq1[target]=seq1[mid]
但是，细心的同学会发现，不对呀，万一此时mid和target不相同呢，看下面例子
Case2：
3 11 12 13 _ mid
6 9 14 15 16 17 18
1.mid=4,target=2
2.9<13,mid=3,target=2
3.14>13，也就是说我们需要将从14开始的数字，填充到[n1,mid]区间，就变成了 11 12 13 (14) (15)
4.中位数即为seq1[4]=15
Case3：
既然mid有可能会>=n1的情况，那也有可能mid<0呀
4 11 12 13 14 mid
5 1 2 3 4 5
1.mid=4,target=3
2.1<14,mid=target=3
3.2<14,mid=target=2
4.3<13,mid=target=1
5.4<12,mid=target=0
6.5<11，发现mid不可能再减小了，由于5是第mid(4)+1个，所以5刚好就是中位数。
但此时仍然有一个样例没过，发现如下情况没考虑：
Case4：
4 4 5 6 10
5 5 7 8 12 13
1.mid=4,target=3
2.5<10,mid=target=3
3.7<10,如果仅仅更新mid和target，mid和target=2，那么接下来8>6，最后的结果为6，但实际上为7
原因是7比6大，所以7不可能插到6的前面，所以只能7替换掉10。
替换是在mid和target相等的情况下，如果此时mid=4，target=3，那么此时的中位数相当于seq[target+1]。
7比10小，当把7插入到10的前面，mid--，中位数是变为了10，所以不会影响。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
/*
水死了
4 11 12 13 14
5 1 2 3 4 54 11 12 13 14
5 9 10 15 16 174 4 5 6 10
5 5 7 8 12 13
7比10小，但是比6大，那还要用7替换掉10由于直接开4*10^5的数组，最后一个样例会超出内存，所以显然应该只能保存一个数组，不能两个都保存。
那么这就要利用到两个数组都是有序的性质了。4 4 5 6 10
5 5 7 8 12 13
*/
const int maxn=+;
int seq[maxn];int main()
{
int n1,n2;
int a;
scanf("%d",&n1);
for(int i=;i<n1;i++){
scanf("%d",&seq[i]);
}
scanf("%d",&n2);
int mid=(n1+n2+)/-; //即中位数对应的索引为mid-1
int target;
if(mid>=n1)
target=n1-;
else
target=mid;
//printf("mid:%d,target:%d\n",mid,target);
int ans=-;
for(int i=;i<n2;i++){
scanf("%d",&a);
//printf("a:%d\n",a);
if(a<seq[target]){
if(mid>){
if(mid==target && a>=seq[mid-])
seq[mid]=a;
else{
mid--;
if(mid<target)
target--;
}
//printf("mid:%d,target:%d\n",mid,target);
}
else{
/*
mid==0，第二行序列已经读取了mid个
此时a<seq[mid]的话，那么总共有mid+1个数<seq[0]，那么中位数就是a了
*/
ans=a;
break;
}
}
else{
if(mid>=n1){
int left=mid-n1;
seq[n1]=a;
for(int j=n1+;j<=mid;j++){
scanf("%d",&seq[j]);
}
ans=seq[mid];
break;
}
else
ans=seq[mid];
}
}
if(ans==-)
ans=seq[mid];
printf("%d\n",ans);
return ;
}
