Просмотр источника
13_Gs. Межгалактическая война [http://dl.gsu.by/task.jsp?nid=1275848&cid=620] Это стандартная задача на кучу. Надо иметь ввиду, что Extract извлекает минимум из кучи, поэтому если в команде 2 нужно только показывать минимум то можно просто выводить Heap1 который является минимальным. Кроме того, в условиях задачи явно не оговорено, но в 6 и 7 тестах производиться команда на удаление при пустой куче. Чтобы их пройти нужно просто ничего не делать в таком случае. Теоретически можно использовать в качестве кучи multiset {code:title=time1.cpp|borderStyle=solid} #include <bits/stdc++.h> using namespace std; int main() { multiset<int> s; int N,i,a,c; cin >> N ; for (i=0; i<N; i++) { cin >> c; if (c==1) {cin >> a; s.insert(a);}; if (c==2) if (s.empty()) cout << -1 << endl; else cout << *s.begin() << endl; if (c==3) { if (not s.empty())a=*s.begin(); s.erase(s.find(a));}; } } {code} Однако в данной задаче количество элементов N = 1 000 000. А сложность multiset N*LogN получается порядка 20 000 000. И такое решение не проходит по времени уже второй тест. В таких случаях лучше использовать priority_que, сложность которой O(N) {code:title=time2.cpp|borderStyle=solid} #include <bits/stdc++.h> using namespace std; int main() { priority_queue <int> q; int N,i,a,c; cin >> N ; for (i=0; i<N; i++) { cin >> c; if (c==1) {cin >> a; q.push(-a);}; if (c==2) if (q.empty()) cout << -1 << endl; else cout << -q.top() << endl; if (c==3) if (not q.empty()) q.pop(); } } {code} Однако это решение не прошло по времени 7-ой тест. Надо ускорить потоковый ввод магическим заклинанием: iostream::sync_with_stdio(false); cin.tie(NULL); И тогда получаем полное решение задачи {code:title=all.cpp|borderStyle=solid} #include <bits/stdc++.h> using namespace std; int main() { iostream::sync_with_stdio(false); cin.tie(NULL); priority_queue <int> q; int N,i,a,c; cin >> N ; for (i=0; i<N; i++) { cin >> c; if (c==1) {cin >> a; q.push(-a);}; if (c==2) if (q.empty()) cout << -1 << endl; else cout << -q.top() << endl; if (c==3) if (not q.empty()) q.pop(); } } {code} |