PAT (Advanced Level) Practice 1029 Median-蒲公英云

PAT (Advanced Level) Practice 1029 Median

输入不要用cin，用scanf，不然会超时。真的要吐血了，没想到是这个点……
使用cin输入数据时最后一个测试点超时，使用scanf直接89ms过，题限是200ms
在数据量较大时，用scanf能明显减少时间…
不过大部分题超时可能还是因为处理方法不对

这题也不难，使用归并的思想就能解决，主要还是超时的坑，另外下面还有一份我写的使用二分的代码（之前以为超时是方法不对，所以就写了二分），也不复杂，速度也是没话说的。使用scanf是42ms过最后一个用例，哪怕用cin也能100多ms过。这个速度提升就很大了。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#define  maxn 200001
using namespace std;
int a[maxn],b[maxn],la,lb,t[maxn];
int main()
{
    cin>>la;
    for(int i=0;i<la;i++){
        scanf("%d",&a[i]);
    }
    cin>>lb;
    for(int i=0;i<lb;i++){
        scanf("%d",&b[i]);
    }
    int index=(la+lb+1)/2;
    int pa,pb,number;
    pa=pb=0;
    while(pa<la&&pb<lb&&index!=0){
        if(a[pa]>b[pb]){
            number=b[pb];
            pb++;
        }else{
            number=a[pa];
            pa++;
        }
        index--;
    }
    if(index==0){
        cout<<number;
    }else{
       if(pa<la){
            cout<<a[pa+index-1];
       }else if(pb<lb){
            cout<<b[pb+index-1];
       }
    }
    return 0;
}

下面给出我用二分写的代码。

#include <iostream>
#include <algorithm>
#include<stdio.h>
#define  maxn 200002
using namespace std;
int a[maxn],b[maxn],la,lb;
bool hasfind=false;
int findMedian(int index,int low,int high,int a[],int b[],int lb){
    while(low<=high){
        int mid = (low+high)/2;
        if(mid>index){
            high=mid-1;
        }else if(index-mid<=lb&&index-mid+1<=lb){
            if(a[mid]>=b[index-mid]&&a[mid]<=b[index-mid+1]){
                    hasfind=true;
                return a[mid];
            }else if(a[mid]<=b[index-mid]){
                low=mid+1;
            }else if(a[mid]>=b[index-mid+1]){
                high=mid-1;
            }
        }else if(index-mid<=lb){
            if(a[mid]>=b[index-mid]){
                hasfind=true;
                return a[mid];
            }else{
                low=mid+1;
            }
        }else{
            return -1;
        }
    }
    return -1;
}
int main()
{
    cin>>la;
    for(int i=1;i<=la;i++){
        scanf("%d",&a[i]);
    }
    cin>>lb;
    for(int i=1;i<=lb;i++){
        scanf("%d",&b[i]);
    }
    int index=(la+lb+1)/2;
    int median= findMedian(index,1,la,a,b,lb);
    if(hasfind==true){
       cout<<median<<endl;
    }else{
        median = findMedian(index,1,lb,b,a,la);
        cout<<median<<endl;
    }
    return 0;
}