4399 8.14笔试三道题思路

用例都过了 不一定ac 但思路应该没问题

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


struct Entry {
    char type;
    int size = 0;
    vector<Entry> children;
};


Entry parseInput(istream& in) {
    Entry currentEntry;
    in >> currentEntry.type;

    if (currentEntry.type == 'f') {
        in >> currentEntry.size;
    } else if (currentEntry.type == 'd') {
        while (true) {
            char nextType;
            in >> nextType;
            if (nextType == 'e') break;
            in.putback(nextType);
            currentEntry.children.push_back(parseInput(in));
        }
        for (const auto& child : currentEntry.children) {
            currentEntry.size += child.size;
        }   
        sort(currentEntry.children.begin(), currentEntry.children.end(), [](const Entry& a, const Entry& b) {
            return a.size > b.size || (a.size == b.size && a.type < b.type);
        });
    }
    return currentEntry;
}


void printEntry(const Entry& entry) {
    cout << entry.type << " ";
    if (entry.type == 'f') {
        cout << entry.size << " ";
    } else if (entry.type == 'd') {
        for (const auto& child : entry.children) {
            printEntry(child);
        }
        cout << "e ";
    }
}


int main() {
    Entry root = parseInput(cin);


    printEntry(root);
    cout << endl;


    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;


struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};




TreeNode* buildTree(const vector<int>& arr, int index) {
    if (index >= arr.size() || arr[index] == -1) return nullptr;  // 检查空节点


    TreeNode* node = new TreeNode('a' + arr[index]);
    node->left = buildTree(arr, 2 * index + 1);
    node->right = buildTree(arr, 2 * index + 2);
    return node;
}


string ans = "{";


void dfs(TreeNode* root, string path) {
    if (!root) return;


   
    path = root->val + path;




    if (!root->left && !root->right) {
        ans = min(ans, path);
        return;
    }


    dfs(root->left, path);
    dfs(root->right, path);
}


int main() {
    vector<int> arr = {1, 0, 3, 4, 5, -1, -1, -1, -1, -1, 2};  


    TreeNode* root = buildTree(arr, 0);
    dfs(root, "");


    cout << ans << endl;  // 
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;


struct Task {
    int id;
    int arrival;
    int duration;
};


struct Compare {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.duration > t2.duration;
    }
};


struct CompletedTask {
    int id;
    int completionTime;
};


int main() {
    vector<Task> tasks = {}; 

    sort(tasks.begin(), tasks.end(), [](const Task& t1, const Task& t2) {
        return t1.arrival < t2.arrival;
    });


    int currentTime = 0;
    priority_queue<Task, vector<Task>, Compare> pq;
    vector<CompletedTask> completedTasks;


    int taskIndex = 0;
    Task currentTask = {0, 0, 0};


    while (taskIndex < tasks.size() || !pq.empty() || currentTask.id != 0) {
        while (taskIndex < tasks.size() && tasks[taskIndex].arrival <= currentTime) {
            pq.push(tasks[taskIndex]);
            taskIndex++;
        }


        if (!pq.empty()) {
            if (currentTask.id == 0 || pq.top().duration < currentTask.duration) {
                if (currentTask.id != 0) {
                    pq.push(currentTask);
                }
                currentTask = pq.top();
                pq.pop();
            }
            currentTask.duration--;
            currentTime++;


            if (currentTask.duration == 0) {
                completedTasks.push_back({currentTask.id, currentTime});
                currentTask = {0, 0, 0};
            }
        } else if (currentTask.id != 0) {
            currentTask.duration--;
            currentTime++;
            if (currentTask.duration == 0) {
                completedTasks.push_back({currentTask.id, currentTime});
                currentTask = {0, 0, 0};
            }
        } else {
            currentTime = tasks[taskIndex].arrival;
        }
    }


    sort(completedTasks.begin(), completedTasks.end(), [](const CompletedTask& a, const CompletedTask& b) {
        return a.completionTime < b.completionTime;
    });


 
    for (const auto& ct : completedTasks) {
        cout <<   ct.id <<  ct.completionTime << endl;
    }
    return 0;
}