Обработка сетевых пакетов
Реализовать обработчик сетевых пакетов.
Вход. Размер буфера 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()
			
						
						
Из-за ограничения размера комментария придётся разбить код на две части.
for (int i = 0; i < numPackets; i++) {
int arrival, duration;
cin >> arrival >> duration;
// Извлекаем из очереди пакеты, обработка которых завершается до прихода этого пакета
while(!packets.empty() && packets.front().endtime