Олимпиадная информатика

Задача «Гистограмма»

2 секунды и 64 Мб памяти

В ходе изучения темы "Редактор электронных таблиц MS Excel" учитель информатики дал школьнику Пете задание изготовить плакат, изображающий простую гистограмму, состоящую из N столбцов разного цвета с заданными высотами hl,h2,..., hN сантиметров. В галантерейном магазине продаются ленты М (N <М) разных цветов с ценами с1, с2,..., см копеек за один сантиметр, каждую ленту можно использовать для изготовления не более одного столбца диаграммы.

Вам нужно так выбрать N лент разного цвета, чтобы суммарная стоимость всех купленных отрезов лент была минимальной.

Формат входного файла input.txt

В первой строке записаны два целых числа N и М(1<=N<=М<=1000) - количество столбцов в гистограмме и количество цветов лент, имеющихся в продаже. Во второй строке записаны N различных целых чисел h1, h2,..., hN - высоты столбцов гистограммы в сантиметрах. Третья строка содержит М различных целых чисел сг, с2,..., см - цены лент в копейках за сантиметр. Все числа в каждой строке записаны через пробел и находятся в диапазоне [1; 1000].

Формат выходного файла output.txt

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

  var
  i, j, s, n, k: longint;a, ak, z, zk: array[0..1006] of longint;

begin
  assign(input, 'input.txt');reset(input);
  assign(output, 'output.txt');rewrite(output);
  read(n, k);
  for i := 1 to n do
    read(a[i]);
  for i := 1 to k do 
    read(z[i]);
  a[0] := 20000;
  ak[1] := 1;
  for i := 2 to n do
  begin
    j := i - 1;
    while a[ak[j]] < a[i] do 
    begin
      ak[j + 1] := ak[j]; 
      dec(j);
    end;
    ak[j + 1] := i;
  end;
  z[0] :=0;
  zk[1] := 1;
  for i := 2 to n do
  begin
    j := i - 1;
    while z[zk[j]] >z[i] do 
    begin
      zk[j + 1] := zk[j];    
      dec(j);   
    end;
   zk[j + 1] := i;
  end;
  for i := n + 1 to k do
  begin
    j := n ;
    while z[zk[j]] > z[i] do 
    begin
      zk[j + 1] := zk[j];
      dec(j);
    end;
    zk[j + 1] := i;
  end;
  s := 0;
  for i := 1 to n do
    s := s + a[ak[i]] * z[zk[i]];
  writeln(s);
  
  for i := 1 to n do
  a[ak[i]]:=zk[i];
  for i:=1 to n do 
    write(a[i],' ');
  close(input);
  close(output);
end.





close
 

Разбор задачи №4 "Гистограмма"

Упорядочим массив H по убыванию, а массив С - по возрастанию. При этом нужно учитывать 2 тонкости:

1)сами массивы нужно сохранить, поэтому сортируем массив индексов и потом работаем с индексам.

2) "Хвост" массива С с номерами больше N сортировать не нужно. Затем найдём сумму попарных произведений N первых элементов отсортированных массивов. При выводе номеров выбранных лент нужно аккуратно работать с индексами.

В нашем районе один из участников предложил (но не осуществил) идею: проходим массивы, в Н находим наибольшее число, а в С - наименьшее, к текущей сумме прибавляем их произведение, сами числа в массивах заменяем в Н нулём, в С - большу 1000, в дополнительном массиве запоминаем найденный индекс из массива С с индексом, найденным в массиве С. По идее должно работать, но не знаю, уложится ли по времени.