tle求调
  • 板块UVA548 树 Tree
  • 楼主iwowo
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/12/17 21:14
  • 上次更新2024/12/17 21:36:40
查看原帖
tle求调
672388
iwowo楼主2024/12/17 21:14
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <chrono>
#include <vector>
#include<map>
#include <cstdlib>
#include <set>
#include <queue>
#include <stack>
#include<bitset>
#include<sstream>
#include<fstream>
#include<cstdio>
using namespace std;
int n, minn = 0x3f3f3f3f3f, ans;
int lc[100001], rc[100001];
int in_order[100001], post_order[100001];
int jianshu(int l1, int r1, int l2, int r2)
{
	if (r1 < l1)
	{
		return -1;
	}
	int root = post_order[r2];
	int p = l1;
	while (in_order[p] != root)
	{
		p++;
	}
	int cnt = p - l1;
	lc[root] = jianshu(l1, p - 1, l2, l2 + cnt - 1);
	rc[root] = jianshu(p + 1, r1, l2 + cnt, r2 - 1);
	return root;
}
void dfs(int u, int sum)
{
	sum += u;
	if (lc[u] == -1 && rc[u] == -1)
	{
		if (sum < minn || (sum == minn && u < ans))
		{
			ans = u;
			minn = sum;
		}
	}
	if (lc[u] != -1)
	{
		dfs(lc[u], sum);
	}
	if (rc[u] != -1)
	{
		dfs(rc[u], sum);
	}
}
int main()
{
	int t;
	char c;
	while (cin >> t >> c)
	{
		
		n = 0;
		in_order[0] = t;
		while (c != '\n')
		{
			cin >> in_order[++n] >> c;
		}
		for (int i = 0; i <= n; i++)
		{
			cin >> post_order[i];
		}
		jianshu(0, n, 0, n);
		dfs(post_order[n], 0);
		cout << ans << '\n';
		memset(in_order, 0, sizeof in_order);
		memset(post_order, 0, sizeof post_order);
		memset(lc, 0, sizeof lc);
		memset(rc, 0, sizeof rc);
		minn = ans = 0x3f3f3f3f3f;
	}
}

//这是洛谷上的UVA548!!!

2024/12/17 21:14
加载中...