Начало
Соревнования
Разбор задачи F. Резервное копирование
Тема: реализация заданного алгоритма, сортировка пузырькомСложность: ниже среднего
На первом этапе алгоритма необходимо отсортировать файлы в порядке уменьшения их размеров, сохраняя исходный порядок в случае одинакового размера. Такая сортировка называется стабильной. Сортировка пузырьком является стабильной, а быстрая сортировка или сортировка выбором – нет. В данном случае количество значений невелико (`N\ ≤\ 1000`), поэтому можно применить сортировку пузырьком, работающую за время `O(N^2)`.
type info=record i,s:longint; end;
var f:array[1..1000] of info; { вместо массива записей можно определить 2 массива }
tmp:info;
i,j,N,S,C:longint;
fl:boolean;
...
fl:=true;
while fl do
begin
fl:=false;
for i:=1 to N-1 do
if f[i].s<f[i+1].s then
begin
tmp:=f[i];
f[i]:=f[i+1];
f[i+1]:=tmp;
fl:=true;
end;
end;
Далее реализуем второй этап, как описано в задаче. Выравнивание размера файла на размер кластера можно реализовать, например, так:
cdsize[j]:=cdsize[j]-f[i].s; cdsize[j]:=cdsize[j]-cdsize[j] mod C;
