TLE求调
查看原帖
TLE求调
408859
miaojintao楼主2025/6/22 22:54
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<map>
using namespace std;

int b[10002],id[10002],le[10002],ri[10002],n,ans=0,min_sum=1e9;

void new_tree(int root,int l,int r){
	if(l>=r) return;
	int x=id[b[root]];
	int m=r-x;
	if(root-m-1>0) le[b[root]]=b[root-m-1];
	if(root-1>0) ri[b[root]]=b[root-1];
	new_tree(root-m-1,l,x-1);
	new_tree(root-1,x+1,r);
}

void dfs(int cur,int sum){
	sum+=cur;
	if(!le[cur] && !ri[cur]){
		if(sum<min_sum || (sum==min_sum && cur<ans)){
			ans=cur;min_sum=sum;
		}
	}
	if(ri[cur]) dfs(ri[cur],sum);
	if(le[cur]) dfs(le[cur],sum);
}

int main(){
	string s,t;
	while(getline(cin,s)){
		getline(cin,t);
		min_sum=1e9;ans=0;
		memset(b,0,sizeof(b));
		memset(id,0,sizeof(id));
		memset(le,0,sizeof(le));
		memset(ri,0,sizeof(ri));
		int ls=s.length(),lt=t.length();
		int m=0,cnt=0;
		for(int i=0;i<ls;i++){
			if(isdigit(s[i])){
				m=m*10+s[i]-'0';
			}
			if(!isdigit(s[i]) || i==ls-1){
				if(m) id[m]=++cnt;
				m=0;
			}
		}
		cnt=0,m=0;
		for(int i=0;i<lt;i++){
			if(isdigit(t[i])){
				m=m*10+t[i]-'0';
			}
			if(!isdigit(t[i]) || i==lt-1){
				if(m) b[++cnt]=m;
				m=0;
			}
		}
		n=cnt;
		new_tree(n,1,n);
		dfs(b[n],0);
		cout<<ans<<endl;
	}
	return 0;
}
2025/6/22 22:54
加载中...