PAT A1029

﹏ヽ暗。殇╰゛Y 2022-03-07 10:24 201阅读 0赞

![clipboard.png][]  
起先自己想尝试性的直接排序找中位数，内存直接超限；

其实这道题可以采用归并排序的思路来做：  
但是示例依旧白给。。。不过还是展现了一种思想，代码如下：

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<vector>
    #include<algorithm>
    using namespace std;
    using std::vector;
    const int maxn=1000010;
    const int INF=0x7fffffff;
    int a[maxn];
    int b[maxn];
    int main(){
        int n,m;
        scanf("%d",&n);
        int index=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&b[i]);
        }
        a[n]=b[m]=INF;
        int i=0,j=0,ct=0;
        int mid=(m+n-1)/2;
        while(ct<mid){
            if(a[i]<b[j]){
                i++;
            }else
                j++;
            ct++;
        }
        if(a[i]<b[j]){
            printf("%d\n",a[i]);
        }else{
            printf("%d\n",b[j]);
        }
        system("pause");
        return 0;
    }

网上给出了一种示例，能够完全AC；

#include <iostream>
    using namespace std;
    int k[200005];
    int main(){
        int n, m, temp, count = 0;
        cin >> n;
        for (int i = 1; i <= n; i++)
            scanf("%d", &k[i]);
        k[n + 1] = 0x7fffffff;
        cin >> m;
        int midpos = (n + m + 1) / 2, i = 1;
        for (int j = 1; j <= m; j++) {
            scanf("%d", &temp);
            while (k[i] < temp) {
                count++;
                if (count == midpos) cout << k[i];
                i++;
            }
            count++;
            if (count == midpos) cout << temp;
        }
        while (i <= n) {
            count++;
            if (count == midpos) cout << k[i];
            i++;
        }
        return 0;
    }

具体的思路就是，输入第一个序列；  
在输入第二个序列的时候进行判断，主要的判断逻辑为：  
如果输入的值小于第一个序列的相应值，cout++，跳过该值；  
如果大于相应值，进行向后判断，cout计算增加的值；  
如果发现途中cout的值等于中点值，直接进行输出，程序停止；

[clipboard.png]: /images/20220307/78c693c67a7d427ab413cdb8cb0a49f1.png