OJ Board

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define delenter(s) if(s[strlen(s)-1] == '\n') s[strlen(s)-1] = '\x0'

typedef struct {
    int left, right;
}t_tree;

t_tree tree[10008];
int inord[10008], post[10008], n, min, des;

void parse(char *str, int *q) {
     int i, lw=0, len=strlen(str);
     char temp[50];

     for (i=0; i<len; i++) {
         if (str[i] == ' ' && lw) {
            temp[lw] = '\x0';
            q[n++] = atoi(temp);
            lw = 0;
         }
         else if (str[i] != ' ') temp[lw++] = str[i];
     }
     if (lw) {
        temp[lw] = '\x0';
        q[n++] = atoi(temp);
     }
}

int find_post(int q, int x) {
    int i;

    for (i=0; i<n; i++) {
        if (q==post[i]) break;
    }
    return(post[i-x]);
}

void reconstruct(int p, int q, int root) {
     int i;

     for (i=p; i<=q; i++) {
         if (inord[i] == root) break;
     }
     if (i-1 >= p) {
        tree[root].left = find_post(root, q-i+1);
        reconstruct(p, i-1, tree[root].left);
     }
     if (i+1 <= q) {
        tree[root].right = find_post(root, 1);
        reconstruct(i+1, q, tree[root].right);
     }
}

void traverse(int root, int sum) {
     if (tree[root].left) {
        traverse(tree[root].left, sum + tree[root].left);
     }

     if (tree[root].right) {
        traverse(tree[root].right, sum + tree[root].right);
     }

     if (!tree[root].left && !tree[root].right) {
        if (sum <= min) {
           min = sum;
           if (root < des) des = root;
        }
     }
}

void process() {
     memset(tree, 0, sizeof(tree));
     reconstruct(0, n-1, post[n-1]);
     min = des = 2147483647;
     traverse(post[n-1], post[n-1]);
     printf ("%d\n", des);
}

int main() {
    char temp[1000000];

    while (fgets(temp, 1000000, stdin)) {
          delenter(temp);
          n = 0;
          parse(temp, inord);
          fgets(temp, 1000000, stdin);
          delenter(temp);
          n = 0;
          parse(temp, post);
          process();
    }
    return(0);
}

Code: Select all

#include<cstdio>
#include<cstring>
#include<string>
#define max 400000
#define Inf 999999999

struct TreeNode
{
	int key;
	struct TreeNode *left;
	struct TreeNode *right;
};


char s[max*5];
int InOrderPos[max];
int PostOrder[max];
TreeNode Tree;
int MinCost;
int MinLeaf;


TreeNode* Initialize(TreeNode *head)
{head->left=head->right=NULL;	return head;}


TreeNode* Makenode(int item)
{
	TreeNode *newnode=Initialize((TreeNode*)malloc(sizeof(TreeNode)));
	newnode->key=item;
	return newnode;
}

TreeNode* Insert(TreeNode* nodeptr, int newnode, int cost)
{
	if(nodeptr==NULL)
	{
		nodeptr=Makenode(newnode);
		if( (MinCost>cost+newnode) || (MinCost==cost+newnode && MinLeaf>newnode)) 
		{MinCost=cost+newnode;MinLeaf=newnode;}
		return nodeptr;
	}
	if(nodeptr->key==MinLeaf)MinCost=Inf;
	if(InOrderPos[newnode]<InOrderPos[nodeptr->key]) 
		nodeptr->left =  Insert(nodeptr->left ,newnode,cost+nodeptr->key);
	if(InOrderPos[newnode]>InOrderPos[nodeptr->key]) 
		nodeptr->right = Insert(nodeptr->right,newnode,cost+nodeptr->key);
	return nodeptr;
}


int main()
{
	int strpos;
	int sl;
	int nodenum;
	int node;
	
	freopen("ip.txt","r",stdin);
	while(gets(s))
	{
		nodenum=0;
		sl=strlen(s);
		strpos=0;
		
		while(strpos<sl &&!isdigit(s[strpos]))strpos++;
		while(strpos<sl){
			sscanf(s+strpos,"%d",&node);
			nodenum++;
			InOrderPos[node]=nodenum;
			while(strpos<sl && isdigit(s[strpos]))strpos++;
			while(strpos<sl &&!isdigit(s[strpos]))strpos++;
		}
		
		for(int c1=1;c1<=nodenum;c1++) scanf("%d",&PostOrder[c1]);
		getchar();

		Initialize(&Tree);
		Tree.key=PostOrder[nodenum];
		MinCost=Inf;
		MinLeaf=Tree.key;
		for(int c2=nodenum-1;c2>0;c2--) Insert(&Tree,PostOrder[c2],0);
		printf("%d\n",MinLeaf);
	}
	return 0;
}

Code: Select all

4 11 2 1 3 9 6
11 4 2 9 6 3 1
4 11 2 1 3 8 6
11 4 2 8 6 3 1
5 7 1
5 7 1

Code: Select all

11
8
5

Code: Select all

if (sum <= min) 
{ 
      min = sum; 
      if (root < des) des = root; 
}