排队问题 (搜索)

r囧r小猫 2022-06-18 07:08 216阅读 0赞

个子高矮不同的12个人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

思路：全排列筛选掉条件可行，12个数要等2分钟左右吧，要是只填答案的话，这个方法还是可以的

#include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	int a[12]={0,1,2,3,4,5,6,7,8,9,10,11},cnt=0;
    	do
    	{
    		if (a[0]<a[1] && a[1]<a[2]&&a[2]<a[3]&&a[3]<a[4]&&a[4]<a[5]
    		&&a[6]<a[7]&&a[7]<a[8]&&a[8]<a[9]&&a[9]<a[10]&&a[10]<a[11]
    		&&a[6]>a[0] && a[7]>a[1] && a[8]>a[2] && a[9]>a[3]&&a[10]>a[4]&&a[11]>a[5])
    		{
    			cnt++;
    		}
    	}while (next_permutation(a,a+12));
    	cout<<cnt;
    	return 0;
    }

深搜判断了好多 条件,速度较快

#include<iostream>
    #include<algorithm>
    using namespace std;
    int a[12],cnt=0,v[12]={0};
    int check(int x)
    {
    	int i,j;
    	if (x==1)
    	 return 0;
    	if (x>=2)
    	{
    		if (a[0]>a[1])
    		 return 1;
    	}
    	if (x>=3)
    	{
    		if (a[1]>a[2])
    		 return 1;
    	}
    	if (x>=4)
    	{
    		if (a[2]>a[3])
    		 return 1;
    	}
    	if (x>=5)
    	{
    		if (a[3]>a[4])
    		 return 1;
    	}
    	if (x>=6)
    	{
    		if (a[4]>a[5])
    		 return 1;
    	}
    	if (x>=7)
    	{
    		if (a[6]<a[0])
    		 return 1;
    	}
    	if (x>=8)
    	{
    		if (a[6]>a[7] || a[7]<a[1])
    		 return 1;
    	}
    	if (x>=9)
    	{
    		if (a[7]>a[8] || a[8]<a[2])
    		 return 1;
    	}
    	if (x>=10)
    	{
    		if (a[8]>a[9] || a[9]<a[3])
    		 return 1;
    	}
    	if (x>=11)
    	{
    		if (a[9]>a[10] || a[10]<a[4])
    		 return 1;
    	}
    	if (x>=12)
    	{
    		if (a[10]>a[11] || a[11]<a[5])
    		 return 1;
    	}
    	return 0;
    }
    void dfs(int x,int y)
    {
    	int i,j;
    	if (x>=12&&!check(x)) //最后还剩一个12也要检测是否正确 
    	{
    		cnt++;
    		return ;
    	}
    	
    	if (check(x))
    	{
    		return ;
    	}
    	for (i=0; i<12; i++)
    	{
    		if (!v[i])
    		{
    			a[x] = i;
    			v[i] = 1;
    			dfs(x+1,y+1);
    			v[i] = 0;
    		}
    	}
    }
    int main()
    {
    	dfs(0,0);
    	cout<<cnt;
    	return 0;
    }