то arrs.insert(it, std::move(temp)) будет работать за O(1)? я правильно понял?
Да
bool comp(const vector<int>& a, const vector<int>& b){ return a[a.size() - 1] > b[b.size() - 1]; } void shift_down(std::list<std::vector<int>>& arr){ // O(logK) vector<int> temp = std::move(*arr.begin()); // O(1) arr.pop_front(); // O(1) if(temp.empty()) return; auto it = std::upper_bound(arr.begin(), arr.end(), temp, comp); // O(logK) ?? arr.insert(it, std::move(temp)); // O(1) } а такая штука за O(logk), где k - arrs.size()?
Тут много операций, какую надо оценивать?
Ну вроде да, если я ничего не пропустил
Обсуждают сегодня