C/C++

Обработка пакетов через контейнер «очередь» продолжение?

ребят так и не получил ответ на свой вопрос в чём дело помогите решить

Обработка сетевых пакетов
Реализовать обработчик сетевых пакетов.
Вход. Размер буфера 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()
Помимо того, что указано в предыдущем ответе, в программе логическая ошибка. Код
 int realStart = max(startTime, arrival); 
ошибочно полагает, что текущий пакет будет обработан в момент realStart, совершенно не учитывая время обработки пакетов, находящихся в текущий момент в очереди. Ошибочность такого подхода видна на примере входа
 1 3
0 10
1 1
2 1
Обработаться должен только первый пакет («пакет освобождает место в буфере сразу же, как компьютер заканчивает его обработку»), остальные пакеты должны быть отброшены.

Другая проблема состоит в том, что сообщение о том, что пакет отброшен, должно выводиться после сообщений о предыдущих пакетах. Чтобы добиться этого, есть два пути.

Первый путь — для текущего пакета рассчитать условие его обработки (заполненность буфера в момент прихода пакета) и время начала его обработки, чтобы вывести эту информацию до обработки следующего пакета.

Второй путь — всё равно положить отбрасываемый пакет в очередь, пометив его каким-либо образом. Когда дойдёт очередь до этого пакета, можно проверить пометку и сообщить, что пакет был отброшен.

Я реализовал второй способ, устанавливая длительность отбрасываемого пакета в 0.
 #include   
#include

using namespace std;

typedef struct { int duration; } packet_duration; // См. прим. 1

int main() {
int bufferSize, numPackets;

queue packets; // очередь пакетов
int currentTime = 0;

cin >> bufferSize >> numPackets;

for (int i = 0; i < numPackets; i++) {
int arrival, duration;
cin >> arrival >> duration;

// Убираем пакеты, обработка которых завершается до прихода этого пакета
while (!packets.empty() && currentTime + packets.front().duration 0) {
cout
Дмитрий Колесник
Дмитрий Колесник
12 091
Лучший ответ
Дмитрий Колесник Увы, увы, на некоторых тестах работает неправильно. Всё-таки первый путь оказался лучше. Вроде проверил все возможные ситуации, работает.

Из-за ограничения размера комментария придётся разбить код на две части.
 #include   
#include

using namespace std;

typedef struct { int endtime; } packet_endtime; // См. прим. 1

int main() {
int bufferSize, numPackets;

queue packets; // очередь пакетов
int currentTime = 0;

cin >> bufferSize >> numPackets;
Дмитрий Колесник
   for (int i = 0; i < numPackets; i++) {  
int arrival, duration;
cin >> arrival >> duration;

// Извлекаем из очереди пакеты, обработка которых завершается до прихода этого пакета
while(!packets.empty() && packets.front().endtime
Очевидно, ошибка в том, что вы не инициализируете переменную numPackets. Попробуйте добавить строку cin >> bufferSize >> numPackets; перед циклом с вводом времени прибытия и длительности пакетов.
Кульбачный Александр вы имеете ввиду перед вайлом ?