DL Руководство пользователя
Сравнение страницы - map & multiset (v.2 vs v.3)
Ключ
Эти линии были удалены. Это слово было удалено.
Эти линии были добавлены. Это слово было добавлено.

Просмотр истории страницы


Есть 27 изменений. Просмотреть первое изменение .

 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}\\
 \\
Powered by Atlassian Confluence, the Enterprise Wiki. (Version: http://www.atlassian.com/software/confluence Build:#2.6.1 916) - Ошибка/новая особенность - Свяжитесь с Администраторами