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

[whatever]

День добрый.

Задание:
Коллекцию из N матрешек нужно перевезти на далекое расстояние. Для этого их нужно упаковать, чтобы они занимали как можно меньше места и при этом не гремели. Каждая из матрешек характеризуется своим размером, который задается натуральным числом. Среди них могут быть матрешки одинакового размера. Вы можете их вставлять друг в друга по такому правилу: если первая матрешка имеет размер L, то она может быть вставлена в матрешку размера L+1. Вложенность может быть сколь угодно большой. Например, если вы имеете три матрешки размера 10, 11 и 12, то можете сделать из них одну размера 12, положив первую во вторую, а затем вторую (с первой внутри) в третью. А если же у вас в наличии матрешки размера 10, 20 и 21, то из них можно получить только две упакованные матрешки. Ваша задача узнать, какое минимальное количество матрешек можно получить.

Входные данные
В первой строке входного файла задано целое число N (0 < N ≤ 10^5). В следующей строке через пробел записаны N натуральных чисел, каждое из которых не превышает 10^9— размеры матрешек.

Выходные данные
В выходной файл необходимо вывести одно целое число — минимальное количество упакованных матрешек.


В общем не долго думая решаю:

program Project1;
{$APPTYPE CONSOLE}
uses
  SysUtils;

type
  Mass=array of integer;
var
  T:textfile;
  i,j,k,n:integer;
  m:mass;
begin
  if fileexists('input.txt') then
    begin
      assignfile(T,'input.txt');
      reset(T);
      readln(T,i);
      setlength(m,i);
      i:=0;
      while not EOF(T) do
        begin
          read(T,m[i]);
          i:=i+1;
        end;
      close(T);
      for i:=high(m)-1 downto 0 do
        for j:=0 to i do
          if m[j]>m[j + 1] then
            begin
              n:=m[j];
              m[j]:=m[j+1];
              m[j+1]:=n;
            end;
      //Есть отсортированный массив
      n:=1;
      for i:=0 to high(m)-1 do
        if m[i+1]-m[i]<>1 then n:=n+1;

//      for i:=0 to high(m) do write(m[i],' ');
      assignfile(T,'output.txt');
      rewrite(T);
      write(T,n);
      close(T);
    end
  else
    begin
      writeln('input.txt not found');
      readln
    end;
end.

Затем пишу прогу для создания input.txt:

program Project1;
{$APPTYPE CONSOLE}
uses
  SysUtils;
type
  mass=array of integer;
var
  T:textfile;
  i,n:integer;
  m:mass;
begin
randomize;
assignfile(T,'input.txt');
rewrite(T);
readln(n);
writeln(T,n);
for i:=0 to n do write(T,1+random(1000000000),' ');
close(T);
end.

Собственно проблема в том, что если в инпуте 100000 (максимум) значений, программа думает очень долго, а в требованяих "Максимальное время работы на одном тесте: 1 секунда". Как я понял, происходит это из-за сортировки.

В общем нужен другой алгоритм решения, просто на словах, писать программу за меня не надо (я понимаю, что никто и так не стал бы, но все таки :D)

[veniside]

Сортировку можно пофиксить, методов дофига, но проблема не в этом. Основная проблема вот тут:

n:=1;
for i:=0 to high(m)-1 do
  if m[i+1]-m[i]<>1 then n:=n+1;

Какое будет n для отсортированного массива m = (1, 1, 1, 2, 2, 2, 3, 3, 3)? Примерно 7.
А должно быть какое? Правильно, должно быть 3.

[Вадим Мошев]

Ну, могу предложить вот что.
В массиве посчитать количество последовательностей, таких, что при их упорядочивании соседние её члены отличаются на 1. Оно и будет равно минимальном количеству матрёшек.

[whatever]

veniside, спасибо, поправил:

program Project1;
{$APPTYPE CONSOLE}
uses
  SysUtils;

type
  Mass=array of integer;

function count(m:mass):integer;
var
  i,k:integer;
  nM:mass;
begin
  result:=1;
  setlength(nM,0);
  k:=0;
  for i:=0 to high(m)-1 do
    begin
      if (m[i+1]-m[i]<>1) and (m[i+1]<>m[i]) then result:=result+1;
      if m[i+1]=m[i] then
        begin
          setlength(nM,length(nM)+1);
          nM[k]:=m[i];
          k:=k+1
        end;
    end;

  if length(nM)<>0 then result:=result+count(nM);
end;


var
  T:textfile;
  i,j,k,n:integer;
  m:mass;
begin
  if fileexists('input.txt') then
    begin
      assignfile(T,'input.txt');
      reset(T);
      readln(T,i);
      setlength(m,i);
      i:=0;
      while not EOF(T) do
        begin
          read(T,m[i]);
          i:=i+1;
        end;
      close(T);
      for i:=high(m)-1 downto 0 do
        for j:=0 to i do
          if m[j]>m[j + 1] then
            begin
              n:=m[j];
              m[j]:=m[j+1];
              m[j+1]:=n;
            end;
      //Есть отсортированный массив

//      for i:=0 to high(m) do write(m[i],' ');
      assignfile(T,'output.txt');
      rewrite(T);
      write(T,count(m));
      close(T);
    end
  else
    begin
      writeln('input.txt not found');
      readln
    end;
end.

Теперь вроде бы верно, но опять же рекурсия, штука тормозная, для 1,1,1,1....1 могу горя хапнуть. Пойду по сслыке, искать сортировку пошустрее. Если у кого-нибудь есть другие идеи, пожалуйста, делитесь

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

[Вадим Мошев]

Ну, сначала сортировка (рекомендую Быструю или сортировку Шелла), а потом мой алгоритм.

[whatever]

Ахр*неть, нет слов. Очень быстрая сортировка, спасибо, Вадим. Странно, что про нее в универе не рассказывали. Осталось понять, как она работает, но тут я как-нибудь сам :D. Сейчас попробую избавиться от рекурсии и посчитать последовательности, как ты советовал.

[mMAg]

Ну, для того чтобы отработало за 1 сек, нельзя использовать алгоритм, сложнее чем n*log(n)^k, это очевидно.
сортировку вы, допустим, сделаете слиянием или быструю (но у этой в худшем случае тоже сложность n^2, так что при наличии нужного теста вы тоже запоретесь), но вот далее рекурсия ваша... мне просто лень углубляться в ваш код, если бы на словах объяснили..

Вот пару плохих, требующих доработки мыслей насчет задачи:
вместо прямого решения в лоб, а-ля сортану и найду, рассмотреть сортировку лишь как способ посчитать количество.
как примерно можно было бы решить задачу: создать еще 1 массив, в котором просто проставить значения размеров матрешки, а потом посчитать их количество. далее, обычно, легко придумать, как по такой матрице дать ответ на поставленный в задаче вопрос за линейное время. но вот ограничение на размер 10^9 наводит на мысль о том, что этот способ решения от нас составители старательно спрятали. если хотя бы 10^6...
ладно, возвращаемся к исходным данным. допустим, мы отсортили массив за n*log(n) сортировкой слиянием. далее что? далее помним, что нам нужна "линия". идем по массиву и считаем количество значений. на переходах от одного значения к другому проверяем, рядом ли значения. если да, то какое-то количество матрешек с предыдущего уровня можно упрятать в матрешки следующего. если нет, тогда все матрешки предыдущего добавляются к общему количеству матрешек. далее на текущем уровне считаем количество матрешек. если их больше или равно, чем на предыдущем, тогда все с предыдующего упрячем в текущие, текущие заносим в буфер предыдущих. если меньше, тогда количество предыдущих - количество текущих добавляем к общему количеству матрешек. и так далее.
надеюсь, суть вам ясна, сложность алгоритма n*log(n) на этапе сортировки и n на этапе подсчета, т.е. O(n*log(n) + n) = O(n*log(n)), что вам как раз подойдет.
если что не понятно, я поясню или код напишу, тут на этапе подсчета его кот наплакал.

Кстати, пока писал Вадим Мошев вам весьма дельную мысль подкинул, но он забыл указать, что вам придется посчитать минимальное количество упорядоченных последовательностей, соседние члены которых отличаются на 1, а я вам, считайте, написал как это сделать.