当前位置：首页 > news >正文

最大匹配+vector的应用

news 来源：原创 2024/5/6 11:57:56

非诚勿扰

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<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;

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

void math(vector<int> &l,vector<int> &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<N;j++)
   {
      int h;
   scanf("%d",&h);
   if(h<0)
   L[i].push_back(-h);
   else
   H[i].push_back(h);    
         }     
         sort(L[i].begin(),L[i].end());
         sort(H[i].begin(),H[i].end());
      }    
      math(L[0],H[1]);
      math(L[1],H[0]);
      printf("%d\n",M);
      L[0].clear();//清空； 
      L[1].clear();
      H[0].clear();
      H[1].clear();
      M=0;
   }  
   system("pause");
   return 0;
}