как получить минимум времени?

Question

введите описание изображения здесь

Допустим, у нас есть это дерево, и я хочу вернуть min_time, который я могу получить с заданным бюджетом c. Пример: 350, min_time = 45, 700 min_time = 20, 1000 min_time = 10, если бюджет меньше или больше, чем цены exisitin, просто верните -1. Как можно сделать это за время выполнения O (h), мне нужны идеи, пожалуйста.

double get_min(node * t, double budget){
}

Answer 1

Вы можете использовать дизайн двоичного дерева поиска (BST) в своих интересах.

Для любого узла в BST все значения справа больше, чем этот узел, а слева меньше, чем этот узел.

Вы можете использовать функцию поиска с измененным способом найти узел, который соответствует вашему бюджету.

int largestValueLessThanN(Node* root, int N) 
{ 
    // Base cases 
    if (root == NULL) 
        return -1; 
    if (root->key == N) 
        return N; 
  
    // If root's value is smaller, try in right subtree
    else if (root->key < N) { 
        int k = largestValueLessThanN(root->right, N); 
        if (k == -1) 
            return root->key; 
        else
            return k; 
    } 
  
    // If root's key is greater, return value from left subtree. 
    else if (root->key > N)  
        return largestValueLessThanN(root->left, N);     
}

В вашем случае кажется, что вам нужно найти узел с максимальной ценой, которая меньше указанного бюджета, тогда вы добавляете минимальное время от этого узла.

Вы не упомянули, что произойдет, если бюджет после нахождения необходимого узла достаточно велик, чтобы получить вам еще один узел . Вы можете вычесть цену найденного узла из своего бюджета и снова выполнить ту же операцию, чтобы получить другой узел.