Подразделы

Другие разделы

Дата и время

05/12/2024 02:41:03

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задачи 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;
loading