P1763埃及分数 最后一个测试点TLE,求助大佬!
查看原帖
P1763埃及分数 最后一个测试点TLE,求助大佬!
1066268
ilhxyBrian_05080924楼主2023/10/4 08:28
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int flag,dep,res=1e7,ans[100]={1},tmp[100];
void DFS(long long a,long long b,int d)
{
	if(d>dep)
	{
		if(a) return;
		else flag=1;
		if(res>ans[dep])
		{
			res=ans[dep];
			for(int i=1;i<=dep;i++) 
        		{		
           			tmp[i]=ans[i];
        		 }     
		}
		return;
	}
	int begin=max(ans[d-1]+1,(b-1)/a);
	int end=min(b*(dep-d+1)/a,res);
	for(ans[d]=begin;ans[d]<=end;ans[d]++)
  	 { 
  		DFS(a*ans[d]-b,b*ans[d],d+1);
    	}
}
int main()
{
	int a,b;
	cin>>a>>b;
	for(dep=1;flag==0;dep++)
	{
		DFS(a,b,1);
	}
	for(int i=1;i<dep;i++)
	{
		cout<<tmp[i]<<" ";
	}
} //请大佬帮本蒻蒟优化代码,谢谢!
2023/10/4 08:28
加载中...