1ripi1sumwc - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:07:37Z

rollbackEdits.php mass rollback

194.88.143.66 в 06:23, 1 сентября 2022

2022-09-01T06:23:11Z

Shersh: /* Более простые варианты исходной задачи */ выпилено неправильное решение

2016-06-05T10:44:18Z

‎Более простые варианты исходной задачи: выпилено неправильное решение

Shersh: /* Реализация 2 */

2015-06-10T08:17:16Z

‎Реализация 2

Shersh: /* Реализация 2 */

2015-06-10T08:14:59Z

‎Реализация 2

5.149.158.162 в 21:38, 9 июня 2015

2015-06-09T21:38:23Z

5.149.158.162 в 21:36, 9 июня 2015

2015-06-09T21:36:31Z

5.149.158.162 в 21:25, 9 июня 2015

2015-06-09T21:25:44Z

5.149.158.162 в 21:24, 9 июня 2015

2015-06-09T21:24:58Z

5.149.158.162 в 21:09, 9 июня 2015

2015-06-09T21:09:38Z

← Предыдущая		Версия 16:07, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex>		<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex>

← Предыдущая		Версия 06:23, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex>		<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum w_i C_i</tex>

@@ Строка 22: / Строка 22: @@
 Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>.
 ==Основная задача==
 ===Описание алгоритма===

← Предыдущая		Версия 08:17, 10 июня 2015
Строка 103:		Строка 103:
	<tex> \mathtt{time}\texttt{++}</tex>		<tex> \mathtt{time}\texttt{++}</tex>

		+	Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.
	В начале работы сортируются по <tex>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>.		В начале работы сортируются по <tex>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>.

@@ Строка 83: / Строка 83: @@
 ====Реализация 2====
-{| class="standard"
+* <tex>\mathtt{Q}</tex> {{---}} обычная [[Очередь | очередь]], в которой работы изначально располагаются в отсортированном по <tex>r_i</tex> порядке,
-! Очереди !! Пояснения !!
+* <tex>\mathtt{P}</tex> {{---}} [[Приоритетные очереди | приоритетная очередь]] по максимуму.
-Очередь с приоритетами для хранения веса работ подходящих по времени.
+ <tex> \mathtt{time} \leftarrow 1</tex>
-|}
+ <tex> \mathtt{answer} \leftarrow 0</tex>
-Перед началом алгоритма [[Сортировка|отсортируем]] работы по порядку неубывания времени появления и добавляем их в очередь <tex>\mathtt{Q}</tex>.
+В начале работы сортируются по <tex>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>.
 ==См. также==

← Предыдущая		Версия 21:38, 9 июня 2015
Строка 102:		Строка 102:

	pop - функция извлечения элемента из очереди <tex>Q</tex>.		pop - функция извлечения элемента из очереди <tex>Q</tex>.
		+
		+	empty - функция проверяет есть ли в очереди элементы, если их нет то вернет '''true''' в ином случая '''false'''.

	<tex> \mathtt{time} \leftarrow r_1</tex>		<tex> \mathtt{time} \leftarrow r_1</tex>

@@ Строка 108: / Строка 108: @@
        '''if''' Q.head() <tex>\neq null</tex> '''and''' <tex>\mathtt{time} \leqslant </tex> Q.head()
           <tex>\mathtt{time}  \leftarrow</tex> Q.head()
-       '''while''' Q.head() <tex> \leqslant \mathtt{time}</tex>
+      <tex>i \leftarrow </tex> Q.head()
-             P.insert(Q.head().<tex>w</tex>)
+       '''while'''  <tex> r_i  \leqslant \mathtt{time}</tex>
              Q.pop()
        <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \ \cdot </tex> P.extractMax()
        <tex> \mathtt{time++}</tex>

@@ Строка 105: / Строка 105: @@
     <tex> \mathtt{time} \leftarrow r_1</tex>
     <tex> \mathtt{answer} \leftarrow 0</tex>
-    <tex> j \leftarrow 1</tex>
+    '''while''' Q.empty() <tex>=</tex> '''false or''' P.empty() <tex>=</tex> '''false'''
-   '''while''' <tex> S \neq \varnothing </tex>
+      '''if''' Q.head() <tex>\neq null</tex> '''and''' <tex>\mathtt{time} \leqslant </tex> Q.head()
           <tex>\mathtt{time}  \leftarrow</tex> Q.head()
-       '''while''' <tex>r_i \leqslant \mathtt{time}</tex>
+       '''while''' Q.head() <tex> \leqslant \mathtt{time}</tex>
-             P.insert(<tex>w_i</tex>)
+             P.insert(Q.head().<tex>w_i</tex>)
              Q.pop()
        <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \ \cdot </tex> P.extractMax()