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

Версия 1 Egor
на Oct 09, 2016 12:16.

 
в сравнении с
Текущий из Egor
за Oct 09, 2016 12:28.
(показать комментарий)
 
Ключ
Эти линии были удалены. Это слово было удалено.
Эти линии были добавлены. Это слово было добавлено.

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


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

 13_Gs9. Устройство http://dl.gsu.by/task.jsp?nid=1122881&cid=620
  13_Gs9. Устройство [http://dl.gsu.by/task.jsp?nid=1122881&cid=620]
  
 Это стандартная задача на использование кучи.
 Вводим число и помещаем его в кучу, по запросу (число=0), берём из кучи минимальный.
  
В С++ для реализации кучи можно использовать multiset
  В С+\+ для реализации кучи можно использовать multiset
 ( не set, поскольку в данной задаче элементы могут повторяться)
 {code:title=p.cpp|borderStyle=solid}
 #include <bits/stdc++.h>
 using namespace std;
  
 int main()
 {
  multiset<int> s;
  int N,i,a;
  
  cin >> N ;
  for (i=0; i<N; i++)
  {
  cin >> a;
  if (a) s.insert(a);
  else {
  a=*s.begin();
  cout << a << endl;
  s.erase(s.find(a));
  }
  }
}{code}
  
  
  
  }
 {code}
 13_NovS. CROWDED
http://dl.gsu.by/task.jsp?nid=1237652&cid=130
  [http://dl.gsu.by/task.jsp?nid=1237652&cid=130]
 Простейший вариант реализации
 
 - сортируем по возрастанию x
Для каждой точки i выясняем тесно ей или нет следующим образом:
 кидаем в set H1 высоты всех точек, которые лежат слева от I на расстоянии не больше чем D
 кидаем в set H2 высоты всех точек, которые лежат справа от I на расстоянии не больше чем D
 Если оба сета не пусты и оба максимума больше удвоенной высоты текущей точки,
 то инкрементируем ответ
  Для каждой точки i выясняем тесно ей или нет следующим образом:
 кидаем в set H1 высоты всех точек, которые лежат слева от I на расстоянии не больше чем D
 кидаем в set H2 высоты всех точек, которые лежат справа от I на расстоянии не больше чем D
 Если оба сета не пусты и оба максимума больше удвоенной высоты текущей точки,
 то инкрементируем ответ
 {code:title=p.cpp|borderStyle=solid}
 #include <bits/stdc++.h>
 using namespace std;
  
 int main() {
  freopen("crowded.in", "r", stdin);
  freopen("crowded.out", "w", stdout);
  
  int N, D;
  cin >> N >> D;
  
  vector<pair<int, int> > A(N);
  for(int i = 0; i < N; i++)
  cin >> A[i].first >> A[i].second;
  
  sort(A.begin(), A.end());
  
  int j1,j2,result = 0;
  for(int i = 0; i < N; i++)
  {
  set<int> H1, H2;
  j1=i-1;
  while(j1 >= 0 && A[j1].first >= A[i].first - D) H1.insert(A[j1--].second);
  j2=i+1;
  while(j2 < N && A[j2].first <= A[i].first + D) H2.insert(A[j2++].second);
  if ((not H1.empty() && *--H1.end() >= 2 * A[i].second &&
  (not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++;
  }
  cout << result;
}{code}
  }
 {code}
  
 проходит только 5 тестов
  
 попробуем оптимизировать работу с сетами
 ведь при переходе от точки I к следующей можно просто удалять не нужные и добавлять нужные элементы:
  
 а именно
  
 при переходе к следующей точке I
 в правом сете (H2) добавляем все подходящие, а удаляем - i-ую вершину
 в левом сете (H1) добавляем i-1-ую вершину и удаляем все не подходящие
  
 
 Вводим вектором массив координат x и h
 
 {quote} vector<pair<int, int> > A(N);
 for(int i = 0; i < N; i++)
 cin >> A[i].first >> A[i].second;{quote}
  
  {quote}
 vector<pair<int, int> > A(N);
 for(int i = 0; i < N; i++)
 cin >> A\[i\].first >> A\[i\].second;
 {quote}
 Это позволяет сортировать эти два массива x и h параллельно стандартной сортировкой
 
 {quote} sort(A.begin(), A.end());{quote}
  
  {quote}
 sort(A.begin(), A.end());
 {quote}
 Заводим мультимножества (множества, которые могут содержать одинаковые элементы) H1 и H2
 
  {quote}multiset<int> H1, H2;{quote}
  {quote}
 multiset<int> H1, H2;
 {quote}
 Далее в цикле для всех точек в порядке возрастания по x
{code:title=part.cpp|borderStyle=solid}
 int j = 0, k = 0, result = 0;
  {code:title=part.cpp|borderStyle=solid}
 int j = 0, k = 0, result = 0;
  for(int i = 0; i < N; i++)
  {
  while (j2 < N && A[j2].first-A[i].first <= D) H2.insert(A[j2++].second);
  Пока точки с индексом j2 в диапазоне D справа от точки I, добавляем их высоты в H2
  
  H2.erase(A[i].second);
  Удаляем из H2 высоту точки i
  
  if (i>0) H1.insert(A[i-1].second);
  Если точка не крайняя слева, добавляем в H1 высоту предыдущей точки
  
  while (j1 < i && A[i].first-A[j1].first > D) H1.erase (A[j1++].second);
  Пока точки с индексом j1 вне диапазона D слева от точки I удаляем их из H1
  
  
  if ((not H1.empty() && *--H1.end() >= 2 * A[i].second &&
  (not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++;
  Если последний элемент в H1 >= 2*h[i] и
  Последний элемент в H2 >= 2*h[i] - инкрементируем ответ
  
  Последний элемент в мультимножестве, упорядоченном по возрастанию
  - это самый большой
  }
  cout << result;
} {code}
  }
 {code}
 Полный текст решения
 {code:title=all.cpp|borderStyle=solid}
 #include <bits/stdc++.h>
 using namespace std;
  
 int main() {
  freopen("crowded.in", "r", stdin);
  freopen("crowded.out", "w", stdout);
  
  int N, D;
  cin >> N >> D;
  
  vector<pair<int, int> > A(N);
  for(int i = 0; i < N; i++)
  cin >> A[i].first >> A[i].second;
  
  sort(A.begin(), A.end());
  
  set<int> H1, H2;
  int j1=0,j2=0,result = 0;
  for(int i = 0; i < N; i++)
  {
  while (j2 < N && A[j2].first-A[i].first <= D) H2.insert(A[j2++].second);
  H2.erase(A[i].second);
  if (i>0) H1.insert(A[i-1].second);
  while (j1 < i && A[i].first-A[j1].first > D) H1.erase (A[j1++].second);
  if ((not H1.empty() && *--H1.end() >= 2 * A[i].second &&
  (not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++;
  }
  cout << result;
 }{code}
  }
 {code}
Powered by Atlassian Confluence, the Enterprise Wiki. (Version: http://www.atlassian.com/software/confluence Build:#2.6.1 916) - Ошибка/новая особенность - Свяжитесь с Администраторами