Просмотр источника
07_AprS. City Horizon [http://dl.gsu.by/task.jsp?nid=146092&cid=15] Фермер Джон взял своих коров в город\! Коровы впервые увидели горизонт в городе во время заката солнца на фоне прямоугольных зданий. Этот горизонт определяется N (1 <= N <= 40,000) зданиями. Силуэт здания i идет от A_i до B_i (1 <= A_i < B_i <= 1,000,000,000) на высоте H_i (1 <= H_i <= 1,000,000,000). Определите площадь (в квадратных единицах) общего силуэта, сформированного всеми зданиями. Формат ввода: * Строка 1: Одно целое число: N * Строки 2..N+1: Строка i+1 описывает здание i тремя разделенными пробелами числами A_i B_i H_i Пример ввода (файл horizon.in): 4 2 5 1 9 10 4 6 8 2 4 6 3 Формат вывода: * Строка 1: Общая площадь, в квадратных единицах, силуэтов, сформированных всеми N зданиями Пример вывода (файл horizon.out): 16 OUTPUT DETAILS: Первое здание перекрывается с четвертым зданием на площадь 1, поэтому общая площадь есть 3*1 + 1*4 + 2*2 + 2*3 - 1 = 16. Идея решения: Заводим массив x координат начал и концов отрезков. В массиве s для каждой такой точки храним, является ли она началом (Left=1) или концом (Right=2) отрезка. В массиве h храним высоту этого отрезка. kx - количество элементов в этом массиве Сортируем массив x по возрастанию (синхронно перемещаем элементы в массивах s и h) Заводим массив актуальных высот hh (kh - количество элементов в нём). Заносим туда первый элемент из h Ответ = 0 Цикл по I от 2 до kx Увеличиваем ответ на площадь прямоугольника (x\[i\]\-x\[i-1\])*MaxH (здесь MaxH - максимум "актуальных высот" - максимум в hh) Если s\[i\]=Left (начало отрезка) То добавляем высоту этого отрезка в массив hh иначе (конец отрезка) удаляем его высоту из списка актуальных высот {code:title=p1.cpp|borderStyle=solid} {$r-} const MaxN = 40000; Left=1; Right=0; var X,H,HH,s : array [1..2*MaxN] of qword; i,N,A,B,HA,kx,kh : longint; Ans : qword; procedure Put(xt,ht,LR:longint); var i : longint; begin inc(kx); x[kx]:=xt; h[kx]:=ht; s[kx]:=LR; end; procedure Sort; var i,j,t : longint; begin for i:=1 to kx do for j:=1 to kx-1 do if x[j]>x[j+1] then begin t:=x[j]; x[j]:=x[j+1]; x[j+1]:=t; t:=h[j]; h[j]:=h[j+1]; h[j+1]:=t; t:=s[j]; s[j]:=s[j+1]; s[j+1]:=t; end; end; procedure Add(h:longint); begin inc(kh); hh[kh]:=h; end; procedure Delete(h:longint); var i : longint; begin for i:=1 to kh do if hh[i]=h then begin hh[i]:=0; exit; end; end; function MaxH:Qword; var i,max : longint; begin max:=0; for i:=1 to kh do if hh[i]>max then max:=hh[i]; MaxH:=max; end; begin assign(input,'horizon.in'); reset(input); assign(output,'horizon.out'); rewrite(output); readln(N); kx:=0; for i:=1 to N do begin readln(A,B,HA); Put(A,HA,Left); Put(B,HA,Right); end; Sort; Ans:=0; kh:=0; Add(h[1]); for i:=2 to kx do begin inc(Ans,(x[i]-x[i-1])*Maxh); if s[i]=Left then Add(h[i]) else Delete(h[i]); end; writeln(Ans); close(input); close(output); end. {code} Это решение прошло 8 тестов, но не прошло 2 последних теста по времени. Заменим сортировку на быструю. Всё равно последние два теста не прошли по времени. Используем стандартные структуры C+\+ для хранения и обработки данных. Для хранения всех троек (x, h, Left или Right) используем структуру данных Map которая будет отображать x-координату точки в структуру вектор пар - высота (h) - признак левая/правая точка отрезка (открывается или закрывается отрезок с высотой h в это точке ) Другими словами для каждой x-координаты из ввода Map будет хранить вектор пар чисел (h,opens) (opens=1 - начало отрезка, open=0) конец отрезка Объявление MAP с именем M {noformat} map<int,vector<pair<int,int> > > M; {noformat} Объявление переменной - итератора для MAP {noformat} map<int,vector<pair<int,int> > >::iterator im; {noformat} Ввод исходных данных и помещение их в MAP {code:title=map.cpp|borderStyle=solid} cin >> N; while(N--) { cin >> a >> b >> h; M[a].push_back(make_pair(h,1)); M[b].push_back(make_pair(h,0)); } {code} Итератор im затем используется для доступа к элементам, хранящимся в M: {noformat} for (im=M.begin(); im!=M.end(); im++) { ... {noformat} При этом итератор для M по объявлению имеет два указателя b = im->first Первый указывает на очередную x-координату (мы ее рассматриваем как конечную для текущего отрезка) Начальная вначале 0 (a=0), А каждый раз после обработки отрезка она становится следующей начальной (a=b) J?каждой такой x-координатой, после ввода всех исходных данных, связан вектор пар высота - признак начала/конца (открытия/закрытия) текущего отрезка. Чтобы обрабатывать последовательно все элементы этого вектора объявляется итератор вектора {noformat} vector<pair<int,int> >::iterator iv; {noformat} И он используется для организации соответствующего цикла: {noformat} for(iv=(im->second).begin(); iv!=(im->second).end(); iv++) { ... {noformat} Для упорядоченного (по убыванию) хранения высот используем multiset S. Объявление {noformat} multiset<int, greater<int> > S; {noformat} multiset S означает что числа в этом множестве могут повторяться (по условию задачи высоты разных отрезков могут быть равны) \\ Заметим, что в set числа не повторяются. Для работы с multiset используем следующие функции: S.insert(h) // вставить высоту h в S S.erase(S.find(h)) // найти в S высоту h и удалить её \*S.begin() // взять наибольшую высоту из S Заметим, что наибольшая высота берётся за O(1), а insert, find, erase выполняются за O(LogN) Итак для обработки вектора (высота, признак) используется следующий цикл {code:title=vektor.cpp|borderStyle=solid} for(iv=(im->second).begin();iv!=(im->second).end();iv++) { h = iv->first; opens = iv->second; if(opens) S.insert(h); else S.erase(S.find(h)); } {code} im->second - указатель в Map на этот вектор iv - итератор в векторе iv->first берёт первый элемент в текущей паре вектора пар iv->second берёт второй элемент в текущей паре вектора пар Если отрезок открывается, добавляем высоту в Multiset S Иначе (отрезок закрывается), находим текущую высоту h в S и удаляем её оттуда Полный текст решения: {code:title=all.cpp|borderStyle=solid} #include <bits/stdc++.h> using namespace std; map<int,vector<pair<int,int> > > M; map<int,vector<pair<int,int> > >::iterator im; vector<pair<int,int> >::iterator iv; multiset<int, greater<int> > S; int main() { int N,a,b,h,opens; long long s=0; freopen("horizon.in","r",stdin); freopen("horizon.out","w",stdout); cin >> N; while(N--) { cin >> a >> b >> h; M[a].push_back(make_pair(h,1)); M[b].push_back(make_pair(h,0)); } a = 0; for(im=M.begin();im!=M.end();im++) { b = im->first; if(!S.empty()) s += (long long)(b - a)*(*S.begin()); a = b; for(iv=(im->second).begin();iv!=(im->second).end();iv++) { h = iv->first; opens = iv->second; if(opens) S.insert(h); else S.erase(S.find(h)); } } cout << s; return 0; } {code}\\ \\ |