очередь с приоритетом | C++ для приматов

Условие

Условие задачи отражает Вашу задачу: необходимо просто сложить числа. Но это будет унизительно если Вас попросят просто написать такую программу на языке C/C++ для заданного множества чисел. Давайте внесем в задачу оттенок изобретательности.

Введем понятие стоимости для операции сложения. Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа $1$ и $10$ стоит $11$. Стоимость сложения $1,$ $2$ равна $3$. Складывать числа можно разными способами:

$1 + 2 = 3 \left(стоимость = 3\right), 3 + 3 = 6 \left(стоимость = 6\right), Всего = 9 $

$1 + 3 = 4 \left(стоимость = 4\right), 2 + 4 = 6 \left(стоимость = 6\right), Всего = 10 $

$2 + 3 = 5 \left(стоимость = 5\right), 1 + 5 = 6 \left(стоимость = 6\right), Всего = 11 $

Надеемся, Вы поняли Вашу задачу. Вам необходимо сложить все числа так, чтобы суммарная стоимость их сложения была наименьшая.

Код

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue <long long> nums;
    long long n;
    cin >> n;
    long long number = 0;
    for (int i = 0; i < n; i++) {
        cin >> number;
        nums.push(-number);
    }
    long long min_sum = 0;
    long long a = 0;
    long long b = 0;
    while ( !nums.empty() )
    {
        a = nums.top();
        nums.pop();
        if (nums.empty()) break;
        b = nums.top();
        nums.pop();
        min_sum -= a+b;
        nums.emplace(a+b);
        
    }
    cout << " " << min_sum;
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

priority_queue <long long> nums;

long long n;

cin >> n;

long long number = 0;

for (int i = 0; i < n; i++) {

cin >> number;

nums.push(-number);

}

long long min_sum = 0;

long long a = 0;

long long b = 0;

while ( !nums.empty() )

{

a = nums.top();

nums.pop();

if (nums.empty()) break;

b = nums.top();

nums.pop();

min_sum -= a+b;

nums.emplace(a+b);

}

cout << " " << min_sum;

return 0;

}

Решение

Стоимость сложения всех чисел будет минимальной, если на каждом следующем шаге мы будем складывать два наименьшие числа из множества $A$, состоящего из данного ряда чисел и уже вычисленных «частичных сумм». Таким образом, каждый шаг цикла поиска минимальной стоимости сложения будет состоять из нахождения двух минимальных чисел из множества, удаления этих чисел из множества $A$ и добавления в него результата их суммирования. В специальную переменную $min\_sum$ будем также каждый раз добавлять результат этого суммирования. Таким образом, количество элементов во множестве будет с каждым шагом уменьшаться на одно, и в конце, когда в нем останется единственный элемент, переменная $min\_sum$ будет содержать искомую стоимость сложения всех чисел.

Реализовать такой код достаточно просто, если реализовать множество $A$ в виде очереди с приоритетом. Так как в задаче нужны минимальные элементы множества, а очередь располагает элементы в порядке их увеличения, то будем хранить в ней не сами элементы множества $A$, а противоположные им числа.

Задача e-olimp.com №3809. Ссылка на засчитанное решение.

За последние несколько лет электронные очереди прочно вошли в повседневную жизнь. Во многих государственных учреждениях можно встретить терминал, печатающий бумажку с номером, и, не задавая привычный вопрос «Кто последний?«, посетители с помощью электронного табло узнают, сколько еще им ждать и когда наступит их очередь.

Однако, пока такие системы далеки от совершенства. Например, вызывает вопросы стандартный принцип любой очереди: «Первым обслуживается тот, кто первым пришел«. При разработке инновационной ГАС «Очередь» решено было сделать ее такой, что выполнение этого принципа не требуется. Вместо этого, новая система призвана минимизировать количество негатива, приходящегося на чиновника, на прием к которому стоят люди в очереди.

Известно, что у каждого человека есть такой критерий, как раздражительность. Если этот параметр равен [latex]w[/latex], то через [latex]t[/latex] часов ожидания в очереди этот человек обрушит на голову чиновника ровно [latex]wt[/latex] единиц злобы и ругани. Так, если посетителя начнут обслуживать сразу же после его прихода, то чиновник не пострадает, а если посетитель пришел в начале третьего часа, а его обслуживание началось только в начале пятого — количество гнева будет равно [latex]2w[/latex].

Также известно, что на обслуживание каждого посетителя уходит ровно час, а каждый посетитель приходит в начале какого-либо часа. Ваша задача заключается в том, чтобы по данным вам показателям раздражительности и временам прихода посетителей определить, сколько негатива достанется чиновнику при оптимальном порядке обслуживания клиентов.

Входные данные

В первой строке задано одно целое число [latex]t[/latex] — количество случаев, которые вам предстоит обработать. Далее следуют [latex]t[/latex] описаний самих случаев.

Описание каждого случая состоит из: числа [latex]n[/latex] в первой строке — количества посетителей, и [latex]n[/latex] описаний самих посетителей. Для каждого посетителя в отдельной строке указаны два целых числа [latex]r_{i}[/latex] и [latex]w_{i}[/latex] [latex]\left(1\leq r_{i},w_i\leq {10}^{6} \right)[/latex] — номер часа, в начале которого посетитель пришел, и его коэффициент раздражительности, соответственно.

Суммарное количество посетителей во всех случаях одного теста не превосходит [latex]10^{5}[/latex].

Выходные данные

Для каждого случая в отдельной строке выведите ответ — минимальное суммарное количество негатива, которое получит чиновник.

Код программы:

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

pair <long long, long long> v [100010]; // массив пар (время, ярость) поменяла местами, чтобы не писать перегруженный оператор, так как сравнивается по умолчанию по первому значению
priority_queue <pair <long long, long long> > q; // очередь пар (ярость, время)

int main() {
	long long t;
	scanf("%lld", &t);
	while (t--) {
		long long n;
		scanf("%lld", &n);
		long long ans=0;
		for (int i=0; i<n; i++) {
			long long r, w;
			scanf("%lld%lld", &r, &w);
			v[i]=make_pair(r,w);
		}
		sort (v, v+n); // сортируем по времени прибытия
		long long k=0;
		long long tim=1;
		for (; tim<=1000000; ) { // цикл от 1 до максимального количества пришедших
			while (v[k].first==tim) { // если встретился такой человек, пришедший в нужный момент времени
				q.push(make_pair(v[k].second, v[k].first)); // то закидываем его в очередь по ярости (по невозрастанию)
				k++;
				if (k==n) break; // выходим из циклов, если прошли все возможные люди
			}
			if (k==n) break;
			if (q.empty()) {
				if (k<n) tim=max(tim+1, v[k].first); // если очередь уже пуста, но люди не закончились, то время ставим на максимум, чтобы не получить TLE
				else tim++;
			}
			else {
				ans+=(long long)q.top().first*(tim-q.top().second);
				tim++;
				q.pop();
			}
		}
		while (!q.empty()) {
			ans+=(long long)q.top().first*(tim-q.top().second); // если очередь не пуста, а люди уже прийти не могут, то просто запускаем по одному
			tim++;
			q.pop();
		}
		printf("%lld\n", ans);
	}
	return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <utility>

#include <algorithm>

using namespace std;

pair <long long, long long> v [100010]; // массив пар (время, ярость) поменяла местами, чтобы не писать перегруженный оператор, так как сравнивается по умолчанию по первому значению

priority_queue <pair <long long, long long> > q; // очередь пар (ярость, время)

int main() {

long long t;

scanf("%lld", &t);

while (t--) {

long long n;

scanf("%lld", &n);

long long ans=0;

for (int i=0; i<n; i++) {

long long r, w;

scanf("%lld%lld", &r, &w);

v[i]=make_pair(r,w);

}

sort (v, v+n); // сортируем по времени прибытия

long long k=0;

long long tim=1;

for (; tim<=1000000; ) { // цикл от 1 до максимального количества пришедших

while (v[k].first==tim) { // если встретился такой человек, пришедший в нужный момент времени

q.push(make_pair(v[k].second, v[k].first)); // то закидываем его в очередь по ярости (по невозрастанию)

k++;

if (k==n) break; // выходим из циклов, если прошли все возможные люди

}

if (k==n) break;

if (q.empty()) {

if (k<n) tim=max(tim+1, v[k].first); // если очередь уже пуста, но люди не закончились, то время ставим на максимум, чтобы не получить TLE

else tim++;

}

else {

ans+=(long long)q.top().first*(tim-q.top().second);

tim++;

q.pop();

}

while (!q.empty()) {

ans+=(long long)q.top().first*(tim-q.top().second); // если очередь не пуста, а люди уже прийти не могут, то просто запускаем по одному

tim++;

q.pop();

}

printf("%lld\n", ans);

}

return 0;

}

Алгоритм состоит в том, чтобы на каждом моменте времени забирать к себе самого агрессивного из людей в очереди.

Для реализации наиболее подходящей структурой хранения данных является очередь с приоритетом, максимум из которой можно извлечь за [latex]O \left( \log n \right)[/latex], тогда суммарное асимптотическое время решения задачи займёт [latex]O \left( \ n log n \right)[/latex].

Ввод	Вывод
$4$ $10$ $12$ $13$ $11$	$92$
$5$ $100$ $11$ $8$ $30$ $12$	$272$
$4$ $2$ $2$ $2$ $2$	$16$
$6$ $1$ $2$ $3$ $4$ $5$ $6$	$51$

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: очередь с приоритетом

e-olymp 1228. Добавить все

Условие

Входные данные

Выходные данные

Тесты

Код

Решение

Ссылки

Related Images:

e-olimp 3809. ГАС Очередь

Related Images: