dfs只过了样例和#1,#6还TLE,求debug!
查看原帖
dfs只过了样例和#1,#6还TLE,求debug!
956316
77Glorious楼主2024/4/12 20:20
#include<bits/stdc++.h>
using namespace std;
int cnt,start=-1,tmp=-2,a[1000010],b[1000010],n,m; bool vis[1000010];
//start是输入的全排列对应的数 
void dfs(int x)
{
	//tmp是目标值的数 ,cnt是有顺序的数 

	if(x>n)
	{
		cnt++;//当前全排列对应的数 
		bool f=1;//1表示a[]与输入全排列相同 
		if(start!=tmp) 
		{
			 
			for(int i=1;i<=n;i++)
			{
				if(a[i]!=b[i])//如果a[]不是输入的全排列,就退出 
				{
					f=0; break;
				}
			}
			if(f==1) {tmp=cnt; start=tmp;}//如果a[]正好对应输入的全排列就存下来start的值 
		}
		if(cnt==start+m)//cnt到了目标值就输出答案 
		{
			for(int i=1;i<=n;i++)
				cout<<a[i]<<' ';
			exit(0);
		}
		return;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]) 
		{
			vis[i]=1; a[x]=i;
			dfs(x+1);
			vis[i]=0;
		}	
	}//手搓全排列 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>b[i];
	dfs(1);	
	return 0;
}
2024/4/12 20:20
加载中...