Var people: array[1..Max-1] of integer;

I, j, s1, s2, n, p, min: integer;

c: char;

begin

readln(N, P);

for i:=1 to N do Delta[i] := 0;

for i:= 1 to P do begin

repeat read(c) until c = ' ';

repeat read(c) until c = ' ';

readln(s1, s2);

for j:=s1 to s2-1 do

people[j] := people[j] + 1;

end;

min := P;

for i:=1 to N-1 do

if people[i] < min then

min := people[i];

for i:=1 to N-1 do

if people[i] = min then

writeln(i, '-', i+1)

end.

Оба решения имеют небольшие недостатки. В первом используется дополнительный массив Delta (расход памяти), но все циклы простые, не вложенные. Поэтому алгоритм имеет линейную сложность – количество операций при больших N и P возрастает почти по линейной зависимости относительно обеих величин.

Во втором решении мы сэкономили память (нет массива Delta), однако при вводе данных получили вложенный цикл, что можно считать несколько неэффективным по скорости выполнения.

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

33. Нужно завести массивы, в одном из которых будем хранить максимальные баллы по каждой школе, а в другом – число учеников, получивших этот максимальный балл:

const MAX = 99;

Var schMax, schCount: array[1..Max] of integer;

В начале оба массива обнуляются:

for i:=1 to MAX do begin

schMax[i] := 0;

schCount[i] := 0;

end;

В этой задаче фамилии и имена нам не нужны, при чтении их можно пропускать. Дойдя до второго пробела, читаем номер школы и балл в целые переменные sch и ball:

repeat read(c) until c = ' ';

repeat read(c) until c = ' ';

readln(sch, ball);

Если балл текущего ученика равен максимальному, увеличиваем счетчик максимальных баллов для этой школы:

if ball = schMax[sch] then

schCount[sch] := schCount[sch] + 1;

Если балл текущего ученика больше предыдущего максимального, записываем новый максимум и сбрасываем счетчик максимальных баллов для этой школы в единицу:

if ball > schMax[sch] then begin

schMax[sch] := ball;

schCount[sch] := 1;

end;

После чтения всех N строк (в цикле) нужно искать максимум в массиве schMax. Попутно (чтобы не делать второй цикл) ищем наибольшее значение счетчика среди всех школ, у которых наибольший балл. Сначала считаем, что лучшая школа – первая:

ball := schMax[1];

count := schCount[1];

Затем в цикле просматриваем все остальные школы. Если балл равен максимальному, ищем наибольшее значение счетчика:

if (schMax[i] = ball) and (schCount[i] > count) then

count := schCount[i];

Если балл больше предыдущего максимального, запоминаем новое максимальное значение и новое значение счетчика:

if schMax[i] > ball then begin

ball := schMax[i];

count := schCount[i];

end;

В конце программы выводим номера школ, в которых и балл, и счетчик равны найденным максимальным значениям:

for i:=1 to MAX do

if (schMax[i] = ball) and (schCount[i] = count) then

writeln(i)

Вот полная программа:

const MAX = 99;