非诚勿扰（谢庆皇）解题报告

/*某卫视新推一档类似“非诚勿扰”的征婚交友节目，每期节目均有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
*/

这是我调试了很久才出来的题目啊，知道朋友的做法，可就是想证明自己的方法也可以，结果证明我是对的。当然我的做法不是很好，时间795Ms，我朋友的是46Ms，要学习一下。下面先贴我的代码，再贴我朋友的！

#include<iostream>using namespace std;#include<cstdio>#include<cmath>#include<algorithm>int a[100005],b[100005];int main(){int t,n,i,j,k,max=0;freopen("in.txt","r",stdin);cin>>t;while(t--){cin>>n;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i=0;i<n;i++)cin>>a[i];for(i=0;i<n;i++)cin>>b[i];        sort(a,a+n);sort(b,b+n);k=0; //记录配对成功的数量for(i=0,j=n-1;j>=0,i<n;j--)//***排序后a[i]绝对值大的负数在前面，和b[i]正数最大的（在后面）的比较。        {if((a[i]<0)&&(b[j]>0)&&(abs(a[i])>abs(b[j]))){k++;//b[j]=0; 不会再访问了，可以不置0//a[i]=0;i++;}if(a[i]>0||b[j]<0)//退出条件break;}for(i=n-1,j=0;i>=0,j<n;j++) //排序后a[i]大的正数在后面，和b[i]绝对值最大的（在前面）的比较        {if(a[i]>0&&b[j]<0&&abs(a[i])<abs(b[j])){k++;i--;}if(a[i]>0&&b[j]<0&&abs(b[j])<=abs(a[i]))//如果最大的b[j]都比当前的a[i]小，i--，（j--是为了抵消j++）{i--;j--;}if(b[j]>0||a[i]<0){break;}}//****************************************cout<<k<<endl;}return 0;}

#include<stdio.h>#include<iostream>using namespace std;#include<algorithm>#include<math.h>int manh[100002],manl[100002],woh[100002],wol[100002];int main(){int T,i,a,b,c,d,j,ans,x; //freopen("in.txt","r",stdin);scanf("%d",&T); while(T--) { int n;  a=b=c=d=0; scanf("%d",&n);  for(i=0;i<n;i++){  scanf("%d",&x);  if(x<0)   manl[++a]=-x;   else   manh[++b]=x;  }  for(i=0;i<n;i++) {   scanf("%d",&x);  if(x<0)   wol[++c]=-x;   else    woh[++d]=x; }  if(a>0) sort(manl+1,manl+a+1); if(c>0) sort(wol+1,wol+c+1); if(b>0) sort(manh+1,manh+b+1);  if(d>0) sort(woh+1,woh+d+1); j=d; ans=0;  for(i=a;i>=1;i--) {  if(j==0)    break;   if(manl[i]>woh[j])   ans++;  else  i++;  j--; } j=b;  for(i=c;i>=1;i--) {  if(j==0)   break;   if(wol[i]>manh[j]) ans++;   else   i++;  j--; } printf("%d\n",ans);}return 0;}