非诚勿扰

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 134   Accepted Submission(s) : 15

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

某卫视新推一档类似“非诚勿扰”的征婚交友节目，每期节目均有N名男生和N名女生。节目开始前每人都要给出自己的薪水和对另一半的薪水期望（比自己高或者比自己低）。一名男生只能和一名女生配对，并且每人要么和薪水比自己高的异性配对，要么和薪水比自己低的异性配对，如果薪水一样的话两个人是不可能配对成功的。

现请你写一程序，对某期的男女嘉宾配对成功的最大值进行计算。

Input

输入包含多组数据，其中第一行一个整数 T，表示数据组数。

对于每组数据，第一行是正整数N（1≤ N ≤ 100 000），表示男女嘉宾各自的人数；第二行包含N个整数（绝对值大于等于1500并小于等于2500），其绝对值代表男生的薪水，该值如是正数表示该男生只能接受薪水比自己高的女生，如是负数表示他只能接受薪水比自己低的女生；第三行类似第二行，表示的是N个女生各自的薪水和对另一半的期望。

Output

对于每组数据，输出一行，用一个整数表示配对成功的最大值。

Sample Input

3 1 -1800 1800 1 1700 -1800 2 -1800 -2200 1900 1700

Sample Output

0 1 2

代码：

#include
     
       #include
      
        #include
       
         #include
        
          using namespace std;
        
       
      
     

vector
     
       L[2];//L[0]存放男生中希望工资比女生高的，H[0]存放男生中希望工资比女生低的； vector
      
        H[2];//L[1]存放女生中希望工资比男生高的，H[1]存放女生中希望工资男女生低的； int N,M;
      
     

void math(vector
     
       &l,vector
      
        &h)//找l中大于h中最大匹配数； {
       if(l.empty()||h.empty())//为空时返回；    return ;    for(int i=l.size()-1,j=h.size()-1;i>=0;i--,j--,M++)//以l为标准进行匹配，从大到小往前推；    {
         while(j>=0&&h[j]>=l[i])//若有j>=0且l[i]>h[j]时一对匹配成功；   j--;   if(j<0)   return ;        }   }
      
     

int main() {
       int t;    scanf("%d",&t);    while(t--)    {
          scanf("%d",&N);    M=0;    for(int i=0;i<2;i++)    {
          for(int j=0;j