489B - BerSU Ball

链接:

https://codeforces.com/problemset/problem/489/B

题意:

给定一个长度n数列和一个长度m数列,其中差值不超过1的可以配对,求最大配对数

输入

4
1 4 6 2
5
5 1 5 7 9

输出量

3

输入

4
1 2 3 4
4
10 11 12 13

输出量

0

输入

5
1 1 1 1 1
3
1 2 3

输出量

2

解:

第一次暴力dfs直接在T7超时,发现如果每个男孩都遍历女孩超时

修改代码为,先排序男孩女孩,再遍历处理

WA…WA…WA…

进过经过无数次WA后,发现,如果从小到大,把能陪对的都先配对上完全没有问题

所以最后解法:

先排序两个数列,以锚点1(男孩)锚点2(女孩)进行dfs,如果满足配对,就先配对,锚点1,2都增加,女孩序列数小于男孩序列数时,增加循环内j,直到满足配对,或者男孩序列数小于女孩序列数时,就对下一个男孩进行配对(锚点1增加)

最后一次WA发现,因为我给的条件是

if(mao1==n+1||mao2==m+1)

所以如果男孩最后一直大于女孩的话,锚点1会停在n,锚点2会小于等于m,所以增加了一条

else if(j==m) dfs(n,m,mao1+1,j+1,pd);

PS:

假设 1
boy  2 3 4
girl 1 2 3
如果 boy2配对girl2 那只能配对两对
如果 boy2配对girl1 那能配对三对

假设 2
boy  2 3 4
girl 2 3
boy2 无论是否配对girl2,这一组至多配对两对

假设 3 
boy  2 3 5
girl 3 4
boy2 无论是否配对girl3,这一组至多配对两对

所以从小到大时,满足配对优先配对即可

实际代码:

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int boy[105];
//int bookboy[105];
int girl[105];
//int bookgirl[105];
int Max=0;
int dfs(int n,int m,int mao1,int mao2,int pd)
{
	if(mao1==n+1||mao2==m+1)//锚点触底,弹出结果 
	{
		if(pd>Max) Max=pd;
		return 0;
	}
	for(int j=mao2;j<=m;j++)//对当前男孩,遍历<可选>女孩序列 
	{
		//cout<<mao1<<" "<<boy[mao1]<<"---"<<j<<" "<<girl[j]<<endl;
		if(abs(boy[mao1]-girl[j])<=1)//满足配对,直接配对 
		{
			//cout<<mao1<<j<<endl;
			dfs(n,m,mao1+1,j+1,pd+1);//锚点1+=1(下一个男孩),锚点2=j+1(<可选>女孩序列起点改变) 
			break;
		}
		else if(boy[mao1]<girl[j])//如果当前女孩序列数大于男孩且不能配对后,锚点1+=1 (下一个男孩)
		{
			dfs(n,m,mao1+1,j,pd);
			break;
		}
		else if(j==m) dfs(n,m,mao1+1,j+1,pd);//当该男孩序列数比所有<可选>女孩序列数大时直接让锚点2=m+1(进行触底)
		//因为从小到大排序,所以后面男孩一样 
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>boy[i];
	}
	sort(boy+1,boy+n+1);//排序 
	int m;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>girl[i];
	}
	sort(girl+1,girl+m+1);//排序 
	dfs(n,m,1,1,0);//锚点1 -1,锚点2 -1进行dfs 
	cout<<Max<<endl;
}

限制:

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

上一篇:python 使用exchange发送邮件


下一篇:5.4、获取对象信息