Programming Ability Test学习 2-13. 两个有序序列的中位数（25）

2-13. 两个有序序列的中位数（25）

时间限制

120 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A₀, A₁…A_N-1的中位数指A_(N-1)/2的值,即第[(N+1)/2]个数（A₀为第1个数）。

输入格式说明：

输入分3行。第1行给出序列的公共长度N（0<N<=100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式说明：

在一行中输出两个输入序列的并集序列的中位数。

样例输入与输出：

序号	输入	输出
1	5 1 3 5 7 9 2 3 4 5 6	4
2	6 -100 -10 1 1 1 1 -50 0 2 3 4 5	1
3	3 1 2 3 4 5 6	3
4	3 4 5 6 1 2 3	3
5	1 2 1

//

#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
typedef struct Node
{
   int dex;
   int length;
   struct Node * Next;
}node,*Link;



int main()
{
    int N;
    scanf("%d",&N);int N1=N;
    struct Node *head,*tail;
    
    head=(node*)malloc(sizeof(node));
    tail=(node*)malloc(sizeof(node));
    tail->Next=NULL;
    head->Next=tail;
    head->length=N;
    struct Node *pthis,*pthat;
    pthis=head;pthat=pthis;
    //第一个链表 
    int dex;
    while(N--){
    scanf("%d",&dex);
    pthis=(node*)malloc(sizeof(node));
    pthis->dex=dex;
    pthis->Next=pthat->Next;
    pthat->Next=pthis;
    pthat=pthis;
    
    }
    //第二个链表 
    struct Node *head1,*tail1;
    head1=(node*)malloc(sizeof(node));
    tail1=(node*)malloc(sizeof(node));
    tail1->Next=NULL;
    head1->Next=tail1;
    pthis=head1;pthat=pthis;
  
    while(N1--){
    scanf("%d",&dex);
    pthis=(node*)malloc(sizeof(node));
    pthis->dex=dex;
    pthis->Next=pthat->Next;
    pthat->Next=pthis;
    pthat=pthis;
  
    }
    
    
    //遍历 
    pthat=head->Next;
    pthis=head1->Next;
    /*while(pthat!=tail){
        printf("%d",pthat->dex);
        pthat=pthat->Next;
        
    }
    printf("
");
    while(pthis!=tail1){
        printf("%d",pthis->dex);
        pthis=pthis->Next;
    }
    printf("
");
    */
    pthat=head->Next;
    pthis=head1->Next;
    struct Node *small=(pthat->dex>pthis->dex)?pthis:pthat;
    struct Node *big=(pthat->dex>pthis->dex)?pthat:pthis;
    struct Node *last;
    pthis=small;pthat=big;
    
    
    N1=0;
    while(pthis->dex<=pthat->dex&&pthis->Next!=NULL&&pthat->Next!=NULL)   
    {
        last=pthis;
        pthis=pthis->Next;
        if(pthis->dex>pthat->dex)
        {
            struct Node *newPoint=(node*)malloc(sizeof(node));
            newPoint->dex=pthat->dex;
            newPoint->Next=last->Next;
            last->Next=newPoint;
            pthis=newPoint;
            pthat=pthat->Next;
        }
    }
    last=small;
    int k=(2*head->length+1)/2;
    while(last->Next!=NULL)
    {
        //printf("%d",last->dex);
        N1++;
        if(N1==k){printf("%d
",last->dex);break;}
        //if(last->Next->Next!=NULL)printf(" ");
        //else printf("
");
        last=last->Next;
    }
    
    
    return 0;

}