| 07_AprS. City Horizon |
| | http://dl.gsu.by/task.jsp?nid=146092&cid=15 |
| | [http://dl.gsu.by/task.jsp?nid=146092&cid=15] |
| |
| | |
| Фермер Джон взял своих коров в город! Коровы впервые увидели горизонт |
| | Фермер Джон взял своих коров в город\! Коровы впервые увидели горизонт |
| в городе во время заката солнца на фоне прямоугольных зданий. |
| | Этот горизонт определяется N (1 <= N <= 40,000) зданиями. Силуэт |
| | Этот горизонт определяется 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 |
| | пробелами числами A_i B_i H_i |
| |
| Пример ввода (файл horizon.in): |
| |
| 4 |
| 2 5 1 |
| 9 10 4 |
| 6 8 2 |
| 4 6 3 |
| |
| | |
| Формат вывода: |
| | |
| * Строка 1: Общая площадь, в квадратных единицах, силуэтов, |
| | сформированных всеми N зданиями |
| | сформированных всеми 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) |
| | (синхронно перемещаем элементы в массивах 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} |
| | Увеличиваем ответ на площадь прямоугольника (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} |
| | end. |
| {code} |
| Это решение прошло 8 тестов, но не прошло 2 последних теста по времени. |
| Заменим сортировку на быструю. |
| Всё равно последние два теста не прошли по времени. |
| |
| | Используем стандартные структуры C++ для хранения и обработки данных. |
| | Используем стандартные структуры C+\+ для хранения и обработки данных. |
| Для хранения всех троек (x, h, Left или Right) используем структуру данных Map |
| которая будет отображать x-координату точки в структуру вектор пар |
| - высота (h) |
| - признак левая/правая точка отрезка |
| | (открывается или закрывается отрезок с высотой h в это точке ) |
| | (открывается или закрывается отрезок с высотой h в это точке ) |
| |
| Другими словами для каждой x-координаты из ввода Map будет хранить вектор пар чисел |
| (h,opens) (opens=1 - начало отрезка, open=0) конец отрезка |
| |
| Объявление MAP с именем M |
| | {noformat}map<int,vector<pair<int,int> > > M;{noformat} |
| |
| | {noformat} |
| map<int,vector<pair<int,int> > > M; |
| {noformat} |
| Объявление переменной - итератора для MAP |
| | {noformat}map<int,vector<pair<int,int> > >::iterator im;{noformat} |
| |
| | {noformat} |
| map<int,vector<pair<int,int> > >::iterator im; |
| {noformat} |
| Ввод исходных данных и помещение их в MAP |
| {code:title=map.cpp|borderStyle=solid} |
| | cin >> N; |
| | 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 |
| | b = im->first |
| Первый указывает на очередную x-координату |
| (мы ее рассматриваем как конечную для текущего отрезка) |
| Начальная вначале 0 (a=0), |
| А каждый раз после обработки отрезка она становится следующей начальной (a=b) |
| |
| J?каждой такой x-координатой, после ввода всех исходных данных, |
| связан вектор пар высота - признак начала/конца (открытия/закрытия) текущего отрезка. |
| |
| Чтобы обрабатывать последовательно все элементы этого вектора объявляется |
| итератор вектора |
| | |
| {noformat}vector<pair<int,int> >::iterator iv;{noformat} |
| |
| | {noformat} |
| vector<pair<int,int> >::iterator iv; |
| {noformat} |
| И он используется для организации соответствующего цикла: |
| {noformat} |
| for(iv=(im->second).begin(); iv!=(im->second).end(); iv++) |
| { |
| ... |
| |
| {noformat} |
| Для упорядоченного (по убыванию) хранения высот используем multiset S. |
| | Объявление{noformat} |
| | Объявление |
| {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 |
| | 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++) |
| | 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 и удаляем её оттуда |
| | Иначе (отрезок закрывается), находим текущую высоту 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}\\ |
| | } |
| {code}\\ |
| \\ |