Обработка сетевых пакетов
Реализовать обработчик сетевых пакетов.
Вход. Размер буфера size и число пакетов n, а так же две последовательности arrival1, . . . , arrivaln и
duration1, . . . , durationn, обозначающих время поступления и длительность обработки n пакетов.
Выход. Для каждого из данных n пакетов необходимо
вывести время начала его обработки или −1, если пакет
не был обработан (это происходит в случае, когда пакет
поступает в момент, когда в буфере компьютера уже
находится size пакетов).
≤ size
arrive
process
Ваша цель — реализовать симулятор обработки сетевых пакетов.
Для i-го пакета известно время его
поступления arrivali
, а также время durationi
, необходимое на его
обработку. В вашем распоряжении
имеется один процессор, который
обрабатывает пакеты в порядке их
поступления. Если процессор начинает обрабатывать пакет i (что
занимает время durationi), он не прерывается и не останавливается
до тех пор, пока не обработает пакет.
У компьютера, обрабатывающего пакеты, имеется сетевой буфер
размера size. До начала обработки пакеты хранятся в буфере. Если буфер полностью заполнен в момент поступления пакета (есть size пакетов, поступивших ранее, которые до сих пор не обработаны), этот
пакет отбрасывается и уже не будет обработан. Если несколько пакетов поступает в одно и то же время, они все будут сперва сохранены в
буфер (несколько последних из них могут быть отброшены, если буфер заполнится).
Компьютер обрабатывает пакеты в порядке их поступления. Он
начинает обрабатывать следующий пакет из буфера сразу после того,
как обработает текущий пакет. Компьютер может простаивать, если
11
все пакеты уже обработаны и в буфере нет пакетов. Пакет освобождает место в буфере сразу же, как компьютер заканчивает его обработку.
Формат входа. Первая строка входа содержит размер буфера size и
число пакетов n. Каждая из следующих n строк содержит два
числа: время arrivali прибытия i-го пакета и время durationi
,
необходимое на его обработку. Гарантируется, что arrival1 ≤
arrival2 ≤ · · · ≤ arrivaln. При этом может оказаться, что
arrivali−1 = arrivali
. В таком случае считаем, что пакет i − 1 поступил раньше пакета i.
Формат выхода. Для каждого из n пакетов выведите время, когда
процессор начал его обрабатывать, или −1, если пакет был отброшен.
Ограничения. Все числа во входе целые. 1 ≤ size ≤ 105
; 0 ≤ n ≤ 105
;
0 ≤ arrivali ≤ 106
; 0 ≤ durationi ≤ 103
; arrivali ≤ arrivali+1 для всех
1 ≤ i ≤ n − 1.
#include
#include
using namespace std;
int main() {
int bufferSize, numPackets;
queue ends; // очередь окончаний
int startTime = 0; // возможный старт
for (int i = 0; i < numPackets; i++) {
int arrival, duration;
cin >> arrival >> duration;
// выясняем, когда на самом деле можно стартовать пакет
int realStart = max(startTime, arrival);
// Извлекаем из очереди пакеты, которые обработаны на момент старта
while (!ends.empty() && ends.front()
Из-за ограничения размера комментария придётся разбить код на две части.