대권수
Sample Input 3 2 1 4 5 7 6 3 1 2 5 6 7 4 7 8 11 3 5 16 12 18 8 3 11 7 16 18 12 5 255 255
물문제, 하지만 1차원수 그룹 구조수에 익숙해져도 괜찮아!중후반에 따라 나무를 만들고 dfs...
#include
using namespace std;
const int maxv = 10005;
int in_order[maxv], post_order[maxv];
int lchild[maxv], rchild[maxv];
int n;
bool read_list(int *a) {
string line;
if (!getline(cin, line)) return false;
stringstream ss(line);//
n = 0;
int x;
while (ss >> x) a[n++] = x;
return n > 0;
}
int build(int L1, int R1, int L2, int R2) {
if (L1 > R1) return 0;
int root = post_order[R2];
int p = L1;
while (in_order[p] != root) p++;
int cnt = p - L1;//
lchild[root] = build(L1, p - 1, L2, L2 + cnt - 1);
rchild[root] = build(p + 1, R1, L2 + cnt, R2 - 1);
return root;
}
int best, best_sum;
void dfs(int u, int sum) {
sum += u;
if (!lchild[u] && !rchild[u]) {//
if (sum < best_sum || (sum == best_sum && u < best_sum)) {
best = u; best_sum = sum;
}
}
if (lchild[u]) dfs(lchild[u], sum);
if (rchild[u]) dfs(rchild[u], sum);
}
int main() {
while (read_list(in_order)) {
read_list(post_order);
build(0, n - 1, 0, n - 1);
best_sum = 0x3f3f3f3f;
dfs(post_order[n - 1], 0);
cout << best << "
";
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Jupyter 노트북을 Github에 연결이 게시물은 jupyter 노트북을 github에 연결하는 방법을 탐색하고 개인 참조 역할을 합니다. 이 가이드는 당신이 깃허브 계정이 있고, 깃과 커맨드 라인에 대한 기본 지식이 있고, 현재 주피터 노트북을 사용하...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.