比赛 |
20160407树结构练习 |
评测结果 |
AAAAA |
题目名称 |
树 |
最终得分 |
100 |
用户昵称 |
ミント |
运行时间 |
0.008 s |
代码语言 |
C++ |
内存使用 |
0.43 MiB |
提交时间 |
2016-04-07 18:56:04 |
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <sstream>
//#define Left 0
//#define Right 1
//#define In 0
//#define Post 1
//#define Leaves -1
using namespace std;
ifstream fin("sumtree.in");
ofstream fout("sumtree.out");
const int Maxn = 10000 + 20;
const int Maxm = 2 + 1;
const int INF = 0xfffff;
int InArray[Maxn], PostArray[Maxn];
int lArray[2], Ans = INF, AnsNode;
int TreeKount = 1;
class poi
{
public:
int Child[Maxm];
//int Father;
int Value;
}Tree[Maxn];
void Init()
{
memset(Tree, 0, sizeof(Tree));
for(int i=1;i<=Maxn-1;i++)
for(int j=1;j<=2;j++)
Tree[i].Child[j] = -1;
return ;
}
bool GetString(int Temp[], int Flag)
{
string Str;
int TempLength = 0;
int TempNum = 0;
if(!getline(fin, Str))
return false;
stringstream fin(Str);
while(fin>>TempNum)
{
TempLength++;
Temp[TempLength] = TempNum ;
}
//cout<<endl;
lArray[Flag] = TempLength;
//fout<<TempLength<<endl;
return TempLength > 0;
}
void EmptyString(int Array[])
{
for(int i=0;i<Maxn;i++)
Array[i] = 0;
return ;
}
int FindPos(int Array[], int ToFind)
{
for(int i=1;i<=lArray[0];i++)
if(Array[i]==ToFind)
return i;
//return -1;
}
/*int BuildTree(int In[], int Istart, int Iend, int Post[], int Pstart, int Pend)
{
if(Istart<Iend&&Pstart<Pend)
{
int Now = Post[Pend];
int RootPos = FindPos(In, Istart, Iend, Now);
int Temp = RootPos - Istart;
//TreeKount++;
Tree[Now].Child[0] = BuildTree(In, Istart, Istart+Temp, Post, Pstart, Pstart+Temp);
Tree[Now].Child[1] = BuildTree(In, Istart+Temp+1, Iend, Post, Pstart+Temp, Pend);
return Now;
}
return -1;
}*/
void BuildTree(int Root, int In[], int Istart, int Iend, int Post[], int Pstart, int Pend)
{
int Now = Post[Pend];
int RootPos = FindPos(In, Now);
int Temp = RootPos - Istart;
Tree[Root].Value = In[RootPos];
//fout<<RootPos<<endl;
//fout<<Tree[Root].Value<<' ';
//Left
if(RootPos<=Istart)
Tree[Root].Child[0] = -1;
else
{
TreeKount++;
Tree[Root].Child[0] = TreeKount;
BuildTree(TreeKount, In, Istart, RootPos-1, Post, Pstart, Pstart+Temp-1);
}
//Right
if(RootPos>=Iend)
Tree[Root].Child[1] = -1;
else
{
TreeKount++;
Tree[Root].Child[1] = TreeKount;
BuildTree(TreeKount, In, RootPos+1, Iend, Post, Pstart+Temp, Pend-1);
}
return ;
}
void DFS(int Pos, int Sum)
{
Sum += Tree[Pos].Value;
if(Tree[Pos].Child[0]!=-1)
DFS(Tree[Pos].Child[0], Sum);
if(Tree[Pos].Child[1]!=-1)
DFS(Tree[Pos].Child[1], Sum);
if(Tree[Pos].Child[0]==-1&&Tree[Pos].Child[1]==-1)
{
if(Ans>Sum)
{
Ans = Sum;
AnsNode = Pos;
//fout<<Pos<<endl;
}
if(Ans==Sum&&Tree[Pos].Value<Tree[AnsNode].Value)
AnsNode = Pos;
}
return ;
}
void Work()
{
while(GetString(InArray, 0)&&GetString(PostArray, 1))
{
BuildTree(1, InArray, 1, lArray[0], PostArray, 1, lArray[1]);
Ans = INF;
DFS(1, 0);
fout<<Tree[AnsNode].Value<<endl;
//fout<<Ans<<endl;
//fout<<"___________"<<endl;
//fout<<lArray[1]<<endl;
EmptyString(InArray);
EmptyString(PostArray);
}
//for(int i=1;i<=lArray[0];i++)
//fout<<Tree[i].Value<<": "<<Tree[i].Child[0]<<' '<<Tree[i].Child[1]<<endl;
return ;
}
int main()
{
Init();
//Read();
Work();
//Write();
fin.close();
fout.close();
return 0;
}