da govno

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
2.0 kB
12
Indexable
Never
/*

Дан массив, состоящий из букв 'X', 'Y' и 'O'. Необходимо найти кратчайшее 
расстояние между буквами 'X' и 'Y', либо вывести 0, если 'X' либо 'Y' отсутствуют.

*/

#include <vector>

int find_min_dist(const vector<char>& v) {
    long int index_x = -1;
    long int index_y = -1;
    int dist = INT_MAX;
    
    for (size_t i = 0; i < v.size(); ++i) {
        if (v[i] == 'X') {
            index_x = i;
        }
        else if (v[i] == 'Y') {
            index_y = i;
        }
        
        if (index_x >= 0 && index_y >= 0) {
            dist = min<size_t>(dist, abs(index_x - index_y));
        }
        
    }
    if (index_x >= 0 && index_y >= 0)
        return dist;
    else
        return 0;
    
}

// 1) ['X', 'Y', '0']
// 2) ['0', 'X']
// 3) ['0', '0']

/* Нужно слить сортированные по возрастанию списки в один. */

// Описание узла списка
struct Node {
    int val;
    Node* next;
};

N - максимальная длина списка
K - кол-во списков 

T = O(N * K)
// template <typename T, typename C>
// std::set
// insert(...)
// begin() -> it
// erase(it)

Node* sorted_array(const vector<Node*>& v) {
    set<Node*, [](Node* n1, Node* n2){ return n1.val < n2.val; }> sorted_elems;
    for (size_t i = 0; i < v.size(); ++i) {
        if (v[i] != nullptr)
            sorted_elems.insert(v[i]);
    }
    Node* result, *cur_node;
    bool first;
    while(sorted_elems.size() > 0) {
        auto cur_iter = sorted_elems.begin();
        if (first)
            result = *cur_iter;
        else {
            cur_node = result.next;
            first = false;
            cur_node.next = *cur_iter;
            cur_node = cur_node.next;
        }
        sorted_elems.erase(cur_iter);
        if (cur_iter->next != nullptr) 
            sorted_elems.insert(cur_iter->next);
         
    }
    
    return result;
}