Уменьшить время выполнения программы - Pascal (81168)
Формулировка задачи:
Здравствуйте, мне дана задача, на решение которой дан лимит по времени: 400ms. В моем решении на больших числах программа выполняется 401 - 402ms. Тоесть на одну - две милисекунды дольше чем нужно и поэтому задача не проходит. Обидно не правда ли? Помогите мне что то изменить в решении, чтобы программа выполнялась немного быстрее.
Условие
При хранении данных на жестких дисках типа HDD данные группируются по секторам. Все файлы разбиваются на фрагменты, которые в свою очередь записываются в некоторых секторах жесткого диска. При этом сектора, в которых находится один файл не обязательно следуют друг за другом и могут располагаться в произвольном порядке.
Одной из проблем HDD-носителей является то, что магнитная головка должна перемещаться от одного сектора к другому, чтобы считать один файл.
Вам требуется определить время за которое будет считан файл, разбитый на n фрагментов. В i-м секторе записан фрагмент файла номер fi (1<=fi<=n). При этом в различных секторах находятся в различные фрагменты. Будем считать, что изначально магнитная головка находится в секторе, в котором записан первый фрагмент. Считывание происходит следующим образом: сначала считывается первый фрагмент, затем магнитная головка перемещается к сектору, содержащему второй фрагмент, считывается второй фрагмент и так далее пока не будет считан n-й фрагмент. Фрагменты считываются один за другим по порядку от 1-го до n-го.
На перемещение магнитной головки от a-го сектора до b-го уходит |a-b| единиц времени. Временем считывания информации можно пренебречь.
Решение
var a,b,w,f:array[1..200000] of longint; p,n,i,k,l,sch, nom:longint; begin read(n); for i:=1 to n do begin read(a[i]); b[i]:=a[i]; end; for l:=1 to n-1 do for i:=l+1 to n do if a[l] > a[i] then begin p:=a[l]; a[l]:=a[i]; a[i]:=p; end; i:=1; l:=1; while (i<=n) and (l<=n+1) do begin if a[i]=b[l] then w[i]:=l; l:=l+1; if l=n+1 then begin i:=i+1; l:=1; end; end; sch:=0; for i:=2 to n do sch:=sch+abs(w[i]-w[i-1]); writeln(sch); end.
Решение задачи: «Уменьшить время выполнения программы»
textual
Листинг программы
program test; var a: array of longint; i, n, fi, t: longint; begin readln(n); setlength(a, n); for i := 1 to n do begin Read(fi); a[fi - 1] := i; end; t := 0; for i := 1 to n - 1 do t := t + abs(a[i] - a[i - 1]); writeln(t); end.
Объяснение кода листинга программы
- В программе объявляются переменные: a, i, n, fi, t, которые представляют собой массив целых чисел, счетчик, длину массива, индексы, значение времени.
- Чтение входных данных происходит в блоке
readln(n)
, где n - это количество элементов в массиве. - С помощью функции
setlength(a, n)
устанавливается длина массиваa
равной значению переменнойn
. - В цикле
for i := 1 to n do
происходит чтение каждого элемента из входных данных и сохранение его в соответствующем элементе массиваa
. - Значение переменной
t
устанавливается равным нулю. - В цикле
for i := 1 to n - 1 do
происходит вычисление разницы между соседними элементами массиваa
и суммирование этих разниц в значение переменнойt
. - Выводится значение переменной
t
, которое представляет собой время выполнения программы.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д