Просмотр источника
13_Gs9. Устройство [http://dl.gsu.by/task.jsp?nid=1122881&cid=620] Это стандартная задача на использование кучи. Вводим число и помещаем его в кучу, по запросу (число=0), берём из кучи минимальный. В С+\+ для реализации кучи можно использовать multiset ( не set, поскольку в данной задаче элементы могут повторяться) {code:title=p.cpp|borderStyle=solid} #include <bits/stdc++.h> using namespace std; int main() { multiset<int> s; int N,i,a; cin >> N ; for (i=0; i<N; i++) { cin >> a; if (a) s.insert(a); else { a=*s.begin(); cout << a << endl; s.erase(s.find(a)); } } } {code} 13_NovS. CROWDED [http://dl.gsu.by/task.jsp?nid=1237652&cid=130] Простейший вариант реализации - сортируем по возрастанию x Для каждой точки i выясняем тесно ей или нет следующим образом: кидаем в set H1 высоты всех точек, которые лежат слева от I на расстоянии не больше чем D кидаем в set H2 высоты всех точек, которые лежат справа от I на расстоянии не больше чем D Если оба сета не пусты и оба максимума больше удвоенной высоты текущей точки, то инкрементируем ответ {code:title=p.cpp|borderStyle=solid} #include <bits/stdc++.h> using namespace std; int main() { freopen("crowded.in", "r", stdin); freopen("crowded.out", "w", stdout); int N, D; cin >> N >> D; vector<pair<int, int> > A(N); for(int i = 0; i < N; i++) cin >> A[i].first >> A[i].second; sort(A.begin(), A.end()); int j1,j2,result = 0; for(int i = 0; i < N; i++) { set<int> H1, H2; j1=i-1; while(j1 >= 0 && A[j1].first >= A[i].first - D) H1.insert(A[j1--].second); j2=i+1; while(j2 < N && A[j2].first <= A[i].first + D) H2.insert(A[j2++].second); if ((not H1.empty() && *--H1.end() >= 2 * A[i].second && (not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++; } cout << result; } {code} проходит только 5 тестов попробуем оптимизировать работу с сетами ведь при переходе от точки I к следующей можно просто удалять не нужные и добавлять нужные элементы: а именно при переходе к следующей точке I в правом сете (H2) добавляем все подходящие, а удаляем - i-ую вершину в левом сете (H1) добавляем i-1-ую вершину и удаляем все не подходящие Вводим вектором массив координат x и h {quote} vector<pair<int, int> > A(N); for(int i = 0; i < N; i++) cin >> A\[i\].first >> A\[i\].second; {quote} Это позволяет сортировать эти два массива x и h параллельно стандартной сортировкой {quote} sort(A.begin(), A.end()); {quote} Заводим мультимножества (множества, которые могут содержать одинаковые элементы) H1 и H2 {quote} multiset<int> H1, H2; {quote} Далее в цикле для всех точек в порядке возрастания по x {code:title=part.cpp|borderStyle=solid} int j = 0, k = 0, result = 0; for(int i = 0; i < N; i++) { while (j2 < N && A[j2].first-A[i].first <= D) H2.insert(A[j2++].second); Пока точки с индексом j2 в диапазоне D справа от точки I, добавляем их высоты в H2 H2.erase(A[i].second); Удаляем из H2 высоту точки i if (i>0) H1.insert(A[i-1].second); Если точка не крайняя слева, добавляем в H1 высоту предыдущей точки while (j1 < i && A[i].first-A[j1].first > D) H1.erase (A[j1++].second); Пока точки с индексом j1 вне диапазона D слева от точки I удаляем их из H1 if ((not H1.empty() && *--H1.end() >= 2 * A[i].second && (not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++; Если последний элемент в H1 >= 2*h[i] и Последний элемент в H2 >= 2*h[i] - инкрементируем ответ Последний элемент в мультимножестве, упорядоченном по возрастанию - это самый большой } cout << result; } {code} Полный текст решения {code:title=all.cpp|borderStyle=solid} #include <bits/stdc++.h> using namespace std; int main() { freopen("crowded.in", "r", stdin); freopen("crowded.out", "w", stdout); int N, D; cin >> N >> D; vector<pair<int, int> > A(N); for(int i = 0; i < N; i++) cin >> A[i].first >> A[i].second; sort(A.begin(), A.end()); set<int> H1, H2; int j1=0,j2=0,result = 0; for(int i = 0; i < N; i++) { while (j2 < N && A[j2].first-A[i].first <= D) H2.insert(A[j2++].second); H2.erase(A[i].second); if (i>0) H1.insert(A[i-1].second); while (j1 < i && A[i].first-A[j1].first > D) H1.erase (A[j1++].second); if ((not H1.empty() && *--H1.end() >= 2 * A[i].second && (not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++; } cout << result; } {code} |