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
иначе (конец отрезка) удаляем его высоту из списка актуальных высот
{$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.
Это решение прошло 8 тестов, но не прошло 2 последних теста по времени.
Заменим сортировку на быструю.
Всё равно последние два теста не прошли по времени.
Используем стандартные структуры C++ для хранения и обработки данных.
Для хранения всех троек (x, h, Left или Right) используем структуру данных Map
которая будет отображать x-координату точки в структуру вектор пар
- высота (h)
- признак левая/правая точка отрезка
(открывается или закрывается отрезок с высотой h в это точке )
Другими словами для каждой x-координаты из ввода Map будет хранить вектор пар чисел
(h,opens) (opens=1 - начало отрезка, open=0) конец отрезка
Объявление MAP с именем M
Объявление переменной - итератора для MAP
Ввод исходных данных и помещение их в MAP
cin >> N;
while(N--)
{
cin >> a >> b >> h;
M[a].push_back(make_pair(h,1));
M[b].push_back(make_pair(h,0));
}
Итератор im затем используется для доступа к элементам, хранящимся в M:
При этом итератор для M по объявлению имеет два указателя
b = im->first
Первый указывает на очередную x-координату
(мы ее рассматриваем как конечную для текущего отрезка)
Начальная вначале 0 (a=0),
А каждый раз после обработки отрезка она становится следующей начальной (a=b)
J?каждой такой x-координатой, после ввода всех исходных данных,
связан вектор пар высота - признак начала/конца (открытия/закрытия) текущего отрезка.
Чтобы обрабатывать последовательно все элементы этого вектора объявляется
итератор вектора
И он используется для организации соответствующего цикла:
Для упорядоченного (по убыванию) хранения высот используем multiset S.
Объявление
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)
Итак для обработки вектора (высота, признак) используется следующий цикл
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));
}
im->second - указатель в Map на этот вектор
iv - итератор в векторе
iv->first берёт первый элемент в текущей паре вектора пар
iv->second берёт второй элемент в текущей паре вектора пар
Если отрезок открывается, добавляем высоту в Multiset S
Иначе (отрезок закрывается), находим текущую высоту h в S и удаляем её оттуда
Полный текст решения:
#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;
}
