U E D R , A S I H C RSS

알고리즘8주숙제/문보창

No older revisions available

No older revisions available



풀이

숙제

~cpp
#include <iostream>  
using namespace std;  
#include <algorithm>  
#include <fstream>  
#include <string>  
#include <vector>  
#include <cmath>  

ifstream fin("test.txt");  

struct Data  
{  
    string data;  
    int p;  
    float priority;  
    bool operator() (const Data* a, const Data* b)  
    {  
        if (a->data < b->data)  
            return true;  
        return false;  
    }  
};  

struct Node  
{  
    string data;  
    int p;  
    int level;  
    Node* left;  
    Node* right;  
};  

vector <Data*> indata;  
Node* root;  
int sum;  

bool compare(const Data* a, const Data* b)  
{  
    if (a->priority > b->priority)  
        return true;  
    return false;  
}  

void input()  
{  
    int number;  
    fin >> number;  

    Data* d;  
    string data;  
    int p;  
    indata.reserve(number);  

    for (int i = 0; i < number; i++)   
    {  
        fin >> data >> p;  
        d = new Data();  
        d->data = data;  
        d->p = p;  
        indata.push_back(d);  
    }  
}  

void insertNode(int i)  
{  
    Node * newNode = new Node();  
    newNode->data = indata[i]->data;  
    newNode->p = indata[i]->p;  
    newNode->left = newNode->right = NULL;  
      
    int l = 1;  
    Node * temp = root;  
    Node * parent = NULL;  
    while (temp)  
    {  
        l++;  
        parent = temp;  
        if (temp->data < newNode->data)  
            temp = temp->right;  
        else if (temp->data > newNode->data)  
            temp = temp->left;  
        else  
            return;  
    }  
    if (parent)  
    {  
        if (parent->data < newNode->data)  
            parent->right = newNode;  
        else  
            parent->left = newNode;  
    }  
    else  
        root = newNode;  
    newNode->level = l;  
}  

void makeTree()  
{  
    root = NULL;  
    for (int i = 0; i < indata.size(); i++)  
        insertNode(i);  
}  

void inorder(Node* t)  
{  
    if (t->left)  
        inorder(t->left);  
    cout << t->data << " ";  
    sum = sum + t->level * t->p;  
    if (t->right)  
        inorder(t->right);  
}  

void show()  
{  
    sum = 0;  
    inorder(root);  
    cout << "\n총 cost : " << sum << endl;  
}  

void priorPrioritySet(int left, int right, int p) 
{ 
    if (left >= right)  
        return; 
    indata[(left + right) / 2]->priority = p; 
    priorPrioritySet(left, (left + right) / 2, p - 41); 
    priorPrioritySet((left+right) / 2 + 1, right, p - 41); 
} 

void process()  
{  
    sort(indata.begin(),indata.end(),Data()); 
    int size = indata.size();  
    priorPrioritySet(0, size-1, 0); 
    float middle = size / 2.0;  
//    for (int i = 0; i < size; i++)  
//       indata[i]->priority += (float)indata[i]->p; 
    sort(indata.begin(),indata.end(),compare);  
    makeTree();  
    show();  
}  

int main()  
{  
    input();  
    process();  
    return 0;  
} 
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0869 sec