PAT (Advanced Level) Practice 1029 Median

今天药忘吃喽~ 2023-07-02 05:25 64阅读 0赞

**输入不要用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;
    }