| | 13_Gs. Межгалактическая война [http://dl.gsu.by/task.jsp?nid=1275848&cid=620] |
| | |
| | Это стандартная задача на кучу. |
| | | Надо иметь ввиду, что Extract извлекает минимум из кучи, поэтому если в команде 2 нужно только показывать минимум то можно просто выводить Heap[1] который является минимальным. |
| | | Надо иметь ввиду, что 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} |
