Рабочий стол > DL Руководство пользователя > ... > Полезные факты о С++ и примеры задач > map & multiset > Information > Сравнить страницу
map & multiset Войти | Зарегистрироваться   Просмотр версии для печати текущей страницы.

Ключ
Эти линии были удалены. Это слово было удалено.
Эти линии были добавлены. Это слово было добавлено.

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


Есть 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) - Ошибка/новая особенность - Свяжитесь с Администраторами