【1029】Median (25 分)

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      //pat上题目和算笔略有修改条件，算笔的内存超限，以下参考柳神代码
     
    
   

    

     

    
    

     

      //key:第二串数字边读边比较。。分"三种"情况，temp那种还是有点懵逼
     
    
   

    

     

    
    

     

      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;//long int的最大长度
     
    
   

    

     

    
    

     

      	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++;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/99222513